Google
This week I caved and decided to learn haskell. I'm about 5 chapters into RWH and its great except for a few topics they gloss over early on (Type classes, $). Luckily my attention was directed here, and I was quickly able to fill in some gaps. Big thanks to f4hy from proggit for the link. Aside from the link there are a couple things that have gotten me really excited. One of which is partial function application.

Partial Function Application


-- file: ch04/Fold.hs
myFoldl :: (a -> b -> a) -> a -> [b] -> a
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)
This is a problem from chapter four of RWH with a lot going on but I'm going to focus specifically on the function application for foldr. If you're new to haskell it looks pretty ambiguous but function application associates to the left and is equivelant to:
(foldr step id xs) z
That's still not much help because a common call to foldr has a value of some sort where the function id is in this case (note: id simply returns whatever argument it is passed). For example.
--zero value of 1
foldr (+) 1 [1,2,3]
--7
So to figure out how this works we can start with the trace of how foldr builds it's thunks up to establish basic understanding:
--included for reference
foldr step zero (x:xs) = step x (foldr step zero xs)
foldr _    zero []     = zero

--foldr (+) 1 [1,2,3]
--step = (+)
--zero = 1
+ 1 (+ 2 (+ 3 (1)))

That's simple enough, now lets apply this to the chapter 4 problem and see where it gets us.
--a custom foldl using foldr
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

--foldr step id [1,2,3]
--step = step
--zero = id
step 1 (step 2 (step 3 (id)))
But how does that damn z fit in here? If evaluating foldr with those three arguments gets me that expression how does that last argument fit in? This is where I got stopped and figured that either this assumption was incorrect or I was missing some fundamental piece of the problem. As it turns out, this is correct but the way in which this statement is evaluated to come up with a result is not obvious, and really amazing. The explanation I got from #haskell (Gracenotes/Eridius) was simple and important for working with haskell in general. All functions with more than a single argument can be decomposed one argument at a time into anonymous functions with the remaining arguments.
--given the following definition of step
step x g a = g (f a x)

--we can count on the following assertions
step = \x g a -> g (f a x)

step 1 = \g a -> g(f a 1)

step 1 id = \a -> id (f a 1)

In the case of our step function and the resulting expression of our foldr, you can see we only give it 2 arguments but step calls for 3. That leaves us with the last argument unassigned, and evaluating that resulting expression looks something like:
step 1 (step 2 (step 3 (id)))

\a3 -> (\a2 -> (\a -> id (f a 3)) (f a2 2)) (f a3 1)
Confusing? Yes its hard to read so walking though it step by step might be useful.
--right most fold operation
step 3 (id)

--only two arguments to the step function
--step x g a = g (f a x) so...
\x g a = g (f a x)

--we know x and g (3 and id respectively)
\a -> id (f a 3)

--having evaluated the rightmost fold we have
step 1 (step 2 (\a -> id (f a 3)))

--having evaluated the 2 rightmost folds
step 1 (\a2 -> (\a -> id (f a 3)) (f a2 x))

--and finally evaluating the last fold we get
\a3 -> (\a2 -> (\a -> id (f a 3)) (f a2 2)) (f a3 1)
At this point we've at least figured out how the function is able to take only two arguments (partial application!) and we can actually plug that back in to our original myFoldl (adding in the example argument values (+), 1, and [1,2,3]) to see what it will look like
--for myFoldl (+) 1 [1,2,3]
myFoldl (+) 1 [1,2,3] = (\a3 -> (\a2 -> (\a -> id (+ a 3)) (+ a2 2)) (+ a3 1))  1
    where step x g a = g (f a x)
And if you look waaay over there on the right we have our third argument! So you can follow the course of the evaluation down from there replacing a3 with 1 and then evaluating (+ a3 1) then passing the result to a2 and (+ a2 2) to a. The laziness of the language allows you to deal with completing your function call at a later date through partial application. This also gives some insight into the type signature syntax of functions
myFunc :: Int -> Int -> Bool
myFunc x y = x == y
What its really saying is that after evaluation of myFunc with its first argument of type Int another function accepting an argument of type Int will be returned. Should you supply another argument to the resulting function a final result of Bool will be returned. I'm not speaking specifically about the execution of the code but rather the nature of the application of functions to the arguments passed.
--different ways to write myFunc
\x -> (\y -> x == y)
\x y -> x == y
myFunc 1 = \y -> 1 == y
myFunc 1 2 = False
If you look at that first one there it looks an awful lot like the type signature. This kind of symmetry to the code and how it works is deeply satisfying to me. I am extremely excited to get my mind wrapped around how to use things like monoids to make your code more stable. Hopefully I'll be back with more as haskell continues to flip my lid.

Published

12 Apr 2009

Tags