Jeremy Gibbons. When is a function a fold or an unfold? Workshop on Generic Programming, July 2001.
We present necessary and sufficient conditions for when a (partial or total) function can be expressed as a fold or an unfold.
The link above is for the slides. You may want to read the paper.
Consider the following two functions:
> either x y zs = elem x zs || elem y zs
> both x y zs = elem x zs && elem y zs
> elem x = foldr ((||).(x==)) False The workshop had many other interesting presentations, by the way.
Can either or both be expressed directly
as a foldr?
(They would be more efficient that way.)
Posted to theory by Ehud Lamm on 5/28/02; 1:24:20 PM