[Haskell-cafe] Working inside the fold

[Greg Buchholz]

    Recently I've been browsing some of Oleg Kiselyov's articles entitled
"Towards the best collection traversal interface"...

    http://okmij.org/ftp/Computation/Continuations.html#enumerator-stream
    
    A programming language system gives us typically one of the two
    interfaces to systematically access elements of a collection. One
    traversal API is based on enumerators -- e.g., for-each, map, filter
    higher-order procedures -- of which the most general is fold. The 
    second approach relies on streams, a.k.a. cursors, lazy lists. 

...where he argues that (since they're both intraconvertible) a default
enumerator/fold choice is better than the lazy-list approach.  I was
sufficiently intrigued I thought I'd take up the challenge and see what
could be done working inside the fold.  This message is literate Haskell
source, for those of you playing at home.  The first thing to do is
define a few folds which will take the place of lists.  I'll start out
with a finite and infinite one...

>numsTo10 f unit = foldr f unit [1..10]
>nats     f unit = foldr f unit [1..]

If you want the sum of the first ten naturals you'd invoke it as...

*Main> numsTo10 (+) 0
55

...and to see that you can convert back to a list...

*Main> numsTo10 (:) []
[1,2,3,4,5,6,7,8,9,10]

That's nice, but the first thing you'll notice is that while there are
numerous list processing functions in the prelude, there are none for
specifically working inside a fold.  Let's try and define a few...

>map_ :: (a -> b) -> (b -> c -> d) -> a -> c -> d
>map_ f g a b = g (f a) b

...so if we want the sum of the first ten squares...

*Main> numsTo10 (map_ (^2) (+)) 0 
385

...or the actual list...

*Main> numsTo10 (map_ (^2) (:)) []
[1,4,9,16,25,36,49,64,81,100]

...Filter is also a nice function...

>filter_ p f a b = if p a then f a b  else b

*Main> numsTo10 (filter_ odd (:)) []
[1,3,5,7,9]

...and we can also play nice with infinity...

>takeWhile_ unit p f a b = if p a
>                          then f a b
>                          else unit

*Main> nats (takeWhile_ [] (<15) (:)) []
[1,2,3,4,5,6,7,8,9,10,11,12,13,14]

...That's a little bit ugly because you have to supply the unit value
(in this case "[]") for the fold to takeWhile_.  The dropWhile_ function
is also a little quirky, since it uses the tupling trick from...

    "A Tutorial on the Universality and Expressiveness of Fold"
     http://citeseer.ist.psu.edu/hutton93tutorial.html

>dropWhile_ p f a (ys, xs) =((if p a 
>                             then ys 
>                             else f a xs), f a xs)

*Main> numsTo10 (dropWhile_ (<5) (:)) ([],[])
([5,6,7,8,9,10],[1,2,3,4,5,6,7,8,9,10])
*Main> numsTo10 (dropWhile_ (<5) (+)) (0,0)
(45,55)

...where the first member of the pair is the desired answer.  If you
want to do more than one thing inside the fold, "fork" might be the
solution (is there a better name?) 

>fork f g z (x,y) = (f z x, g z y)

*Main> numsTo10 (fork (:) (+)) ([],0)
([1,2,3,4,5,6,7,8,9,10],55)
*Main> numsTo10 (fork (filter_ odd (:)) (fork (+) (*))) ([],(0,1))
([1,3,5,7,9],(55,3628800))

...And you can mostly compose these operations, although for infinite
lists you'll hit bottom if anything other than takeWhile_ is the first
function...

>c = nats (takeWhile_ ([],(0,1)) (<20) 
>            (filter_ even (map_ (^2) (fork (:) (fork (+) (*))))))
>         ([],(0,1))

*Main> c
([4,16,36,64,100,144,196,256,324],(1140,34519618525593600))

...So a few generic munging functions can be defined for inside the fold.
I couldn't think of how to define "take" or "drop" or figure out what a
zipWith would mean.  Are there any other interesting functions that
could be defined?  Is there a better way define these functions?  Is
there anything other than curiosity which would motivate someone to use
these functions?


FWIW,

Greg Buchholz