functional programming - Haskell function application and currying -

i interested in learning new languages, fact keeps me on toes , makes me (i believe) better programmer. attempts @ conquering haskell come , go - twice far - , decided time try again. 3rd time's charm, right?

nope. re-read old notes... , disappointed :-(

the problem made me lose faith last time, easy one: permutations of integers. i.e. list of integers, list of lists - list of permutations:

[int] -> [[int]] 

this in fact generic problem, replacing 'int' above 'a', still apply.

from notes:

i code first on own, succeed. hurrah!

i send solution friend of mine - haskell guru, helps learn gurus - , sends me this, told, "expresses true power of language, use of generic facilities code needs". it, drank kool-aid, let's go:

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

hmm. let's break 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, far, good. took me minute understand second line of "ins", ok: places 1st arg in possible positions in list. cool.

now, understand foldr , concatmap. in "real world haskell", dot explained...

(f . g) x 

...as syntax for...

f (g x)  

and in code guru sent, dot used foldr, "ins" function fold "collapse":

*main> let g=concatmap . ins *main> g 1 [[2,3]] [[1,2,3],[2,1,3],[2,3,1]] 

ok, since want understand how dot used guru, try equivalent expression according dot definition, (f . g) x = f (g x) ...

*main> concatmap (ins 1 [[2,3]])  <interactive>:1:11:      couldn't match expected type `a -> [b]'             against inferred type `[[[t]]]'      in first argument of `concatmap', namely `(ins 1 [[2, 3]])'      in expression: concatmap (ins 1 [[2, 3]])      in definition of `it': = concatmap (ins 1 [[2, 3]]) 

what!?! why? ok, check concatmap's signature, , find needs lambda , list, that's human thinking; how ghc cope? according definition of dot above...

(f.g)x = f(g x),  

...what did valid, replace-wise:

(concatmap . ins) x y = concatmap (ins x y) 

scratching head...

*main> concatmap (ins 1) [[2,3]] [[1,2,3],[2,1,3],[2,3,1]] 

so... dot explanation apparently simplistic... dot must somehow clever enough understand in fact wanted "ins" curri-ed away , "eat" first argument - becoming function wants operate on [t] (and "intersperse" them '1' in possible positions).

but specified? how did ghc knew this, when invoked:

*main> (concatmap . ins) 1 [[2,3]] [[1,2,3],[2,1,3],[2,3,1]] 

did "ins" signature somehow conveyed this... "eat first argument" policy?

*main> :info ins ins :: t -> [t] -> [[t]]        -- defined @ b.hs:1:0-2 

i don't see nothing special - "ins" function takes 't', list of 't', , proceeds create list "interspersals". nothing "eat first argument , curry away".

so there... baffled. understand (after hour of looking @ code!) goes on, but... god almighty... perhaps ghc makes attempts see how many arguments can "peel off"?

  let's try no argument "curried" "ins",   oh gosh, boom,    let's try 1 argument "curried" "ins",   yep, works,   must it, proceed) 

again - yikes...

and since comparing languages learning know, how "ins" in python?

a=[2,3] print [a[:x]+[1]+a[x:] x in xrange(len(a)+1)]  [[1, 2, 3], [2, 1, 3], [2, 3, 1]] 

be honest, now... simpler?

i mean, know newbie in haskell, feel idiot... looking @ 4 lines of code hour, , ending assuming compiler... tries various interpretations until finds "clicks"?

to quote lethal weapon, "i old this"...

(f . g) x = f (g x) 

this true. concluded that

(f . g) x y = f (g x y) 

must true, not case. in fact, following true:

(f . g) x y = f (g x) y 

which not same.

why true? (f . g) x y same ((f . g) x) y , since know (f . g) x = f (g x) can reduce (f (g x)) y, again same f (g x) y.

so (concatmap . ins) 1 [[2,3]] equivalent concatmap (ins 1) [[2,3]]. there no magic going on here.

another way approach via types:

. has type (b -> c) -> (a -> b) -> -> c, concatmap has type (x -> [y]) -> [x] -> [y], ins has type t -> [t] -> [[t]]. if use concatmap b -> c argument , ins a -> b argument, a becomes t, b becomes [t] -> [[t]] , c becomes [[t]] -> [[t]] (with x = [t] , y = [t]).

so type of concatmap . ins t -> [[t]] -> [[t]], means function taking whatever , list of lists (of whatevers) , returning list of lists (of same type).