Haskell function application and currying

I am always interested in learning new languages, a fact that keeps me on my toes and makes me (I believe) a better programmer. My attempts at conquering Haskell come and go - twice so far - and I decided it was time to try again. 3rd time's the charm, right?

Nope. I re-read my old notes... and get disappointed :-(

The problem that made me lose faith last time, was an easy one: permutations of integers. i.e. from a list of integers, to a list of lists - a list of their permutations:

[int] -> [[int]]

This is in fact a generic problem, so replacing 'int' above with 'a', would still apply.

From my notes:

I code it first on my own, I succeed. Hurrah!

I send my solution to a good friend of mine - Haskell guru, it usually helps to learn from gurus - and he sends me this, which I am told, "expresses the true power of the language, the use of generic facilities to code your needs". All for it, I recently drank the kool-aid, let's go:

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

Hmm. Let's break this down:

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

OK, so far, so good. Took me a minute to understand the second line of "ins", but OK: It places the 1st arg in all possible positions in the list. Cool.

Now, to understand the foldr and concatMap. in "Real world Haskell", the DOT was explained...

(f . g) x

...as just another syntax for...

f (g x)

And in the code the guru sent, DOT was used from a foldr, with the "ins" function as the fold

haskell functional-programming currying

Edit Report

I'd like to add my two cents. The question and answer make it sound like . is some magical operator that does strange things with re-arranging function calls. That's not the case. . is just function composition. Here's an implementation in Python:

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

It just creates a new function which applies g to an argument, applies f to the result, and returns the result of applying f.

So (concatMap . ins) 1 [[2, 3]] is saying: create a function, concatMap . ins, and apply it to the arguments 1 and [[2, 3]]. When you do concatMap (ins 1 [[2,3]]) you're instead saying, apply the function concatMap to the result of applying ins to 1 and [[2, 3]] - completely different, as you figured out by Haskell's horrendous error message.

UPDATE: To stress this even further. You said that (f . g) x was another syntax for f (g x). This is wrong! . is just a function, as functions can have non-alpha-numeric names (>><, .., etc., could also be function names).

answered 2010-10-07T19:05:49.093

Haskell function application and currying

1 Answer

Your Answer