Haskell: Sending parameters to multiple functions

Question

I am a beginner to Haskell. This is an example from my lectures, where we define our function permu which should produce all permutations of a list.

permu :: [a] -> [[a]]
permu [] = [[]]
permu (x:xs) = concatMap (insertAll x) $ permu xs
insertAll :: a -> [a] -> [[a]]
insertAll = undefined

I'll leave insertAll as undefined for now, as it is not the part that I need help with. My problem is this: concatMap has the type Foldable t => (a -> [b]) -> t a -> [b] and should thus take two parameters. However, insertAll should also take two parameters.

As far as I can tell concatMap takes insertAll x as first parameter and permu xs as the second. This all is good. But it looks to me like insertAll only takes the argument x.

Is it possible that both concatMap and insertAll takes permu xs as their second parameter, or am I missing something?? Thank you!

insertAll x is curried: it's equivallent to \arg -> insertAll x arg. — Aplet123
– Aplet123, Commented Jan 15, 2021 at 15:57
Oh, now I see! I've been trying to google this problem for a while, and getting a name for it helped a lot! — Jonatan Matias Vaara
– Jonatan Matias Vaara, Commented Jan 15, 2021 at 16:11
@JonatanMatiasVaara Sometimes it's helpful to understand that in Haskell all functions always take exactly one argument. What we call "N-ary" functions (N>1) actually are unary functions whose return value is just another (N-1)-ary function. When we call f arg1 arg2 we actually call f with arg1, get the resulting function, and call that with arg2. Indeed, f arg1 arg2 is equivalent to (f arg1) arg2 and to let resultFun = f arg1 in resultFun arg2. — chi
– chi, Commented Jan 15, 2021 at 20:16

Bartek Banachewicz · Accepted Answer · 2021-01-15 17:16:30Z

3

But it looks to me like insert all only takes the argument x.

As the comment mentioned, Haskell functions are curried by default. This makes partial application of them easy - simply providing less arguments than the function "takes" leaves you with a partially applied function that will take the rest.

In your case, partially applying insertAll on x leaves us with a [a] -> [[a]] function, which makes the signature compatible with the first argument of concatMap. The second argument to insertAll is effectively provided within concatMap.

answered Jan 15, 2021 at 17:16

Bartek Banachewicz

39.5k8 gold badges100 silver badges141 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Haskell: Sending parameters to multiple functions

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related