Home » forums » LtU Forum

zip in the point free style

Hi,

I have been recently trying to read the book algebra of programming which discusses a point free style of functional programming which can be quite appealing (via fold functions)- but there are some details which I dont quite understand yet (so far I have only gotten through the first few chapters since I had to go find a book on category theory to understand some of the terminology). The question I have is how do you do things like zip in the point free style especially if you have different fold functions for the two things you wish to zip?

Thanks in advance,

Carter.

By Carter Cheng at 2009-04-02 16:00 | LtU Forum | previous forum topic | next forum topic | other blogs | 6017 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I'm not sure what you mean

I'm not sure what you mean by the "different fold functions for the two things" bit, but (uncurry of) zip :: [a] -> [b] -> [(a,b)] has a nice pointfree characterization as an unfold. I'll leave you the pleasure of working it out from that description!

By jeremygibbons at Fri, 2009-04-03 20:52 | login or register to post comments

Wikipedia

Jeremy is right you should work it out yourself you will get it fairly quickly. Remember the key idea is your test case is, is either list empty? If you can't get it, the wikipedia article on unfold uses zip as an example Anamorphism.

By JeffB at Tue, 2009-04-07 14:58 | login or register to post comments

Thanks guys. I guess I will

Thanks guys. I guess I will look into this a bit further. I guess my main problem is that my fundamentals in this area are a bit lacking. I have been just trying to grapple with the utility of this approach w.r.t. programming.

By Carter Cheng at Tue, 2009-04-07 15:35 | login or register to post comments

another article

Well the utility comes from getting casual about being point free. For example if you are operating on a list of lists and you want to change the elements using f:

map (map f) lss

seeing that map can take a function that acts on lists... allows you to avoid nesting issues. So you don't end up doing something like

h [(v:vs):lss) = ((f v):(h (vs:lss)))
h ([]:lss]) = []:(h lss)
h [] = []

or if you are in a language which allows it something truly hideous like:

for i = 0 to ((size of a)-1)) 
  let velse = size of a[i] - 1
  for j = 0 to velse
    let a[i][j] = f(a[i][j])
   next j
next i

You are doing these exercises to build up mental muscles.

By JeffB at Tue, 2009-04-07 20:32 | login or register to post comments

To be fair...

First class functions do not require point free style.

map (xs -> map f xs) yss

is more fair for comparison to pointy style.

By Matt M at Tue, 2009-04-07 22:07 | login or register to post comments

Thanks. I think I now have a

Thanks. I think I now have a sense of what an unfold might be though my category theory is a bit weak- so I am not yet completely clear on the definitions of catamorphisms and anamorphisms and the full implications of these definitions.

When I meant from a programming perspective I meant in terms of whether it is practicable to write programs in a completely point free manner without referring to entities in a point-wise manner- or does one always have to construct fold/unfold type operators "by hand" which would break the abstraction?

By Carter Cheng at Thu, 2009-04-09 18:36 | login or register to post comments

Not at all

No not at all. Once you have expressed things as map fold you get some wonderful automatic combinations (these are called "fusion"):

For example:

foldr f a . map g = foldr (f.g) a
or in the case that:

1) f is strict
2) f a = b
3) f (g x y) = hx (fy) ;

f . foldr g a = foldr h b

By JeffB at Tue, 2009-04-14 01:58 | login or register to post comments