title: Haskell function application and currying
body: <p>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?</p>
  
  <p>Nope. I re-read my old notes... and get disappointed :-(</p>
  
  <p>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:</p>
  
  <pre><code>[int] -&gt; [[int]]
  </code></pre>
  
  <p>This is in fact a generic problem, so replacing 'int' above with 'a', would still apply.</p>
  
  <p>From my notes:</p>
  
  <p>I code it first on my own, I succeed. Hurrah!</p>
  
  <p>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:</p>
  
  <pre><code>permute :: [a] -&gt; [[a]]
  permute = foldr (concatMap.ins) [[]]
     where ins x []     = [[x]]
           ins x (y:ys) = (x:y:ys):[ y:res | res &lt;- ins x ys]
  </code></pre>
  
  <p>Hmm.
  Let's break this down:</p>
  
  <pre><code>bash$ cat b.hs
  ins x []     = [[x]]
  ins x (y:ys) = (x:y:ys):[ y:res | res &lt;- ins x ys]
  
  bash$ ghci
  Prelude&gt; :load b.hs
  [1 of 1] Compiling Main             ( b.hs, interpreted )
  Ok, modules loaded: Main.
  
  *Main&gt; ins 1 [2,3]
  [[1,2,3],[2,1,3],[2,3,1]]
  </code></pre>
  
  <p>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.</p>
  
  <p>Now, to understand the foldr and concatMap. in "Real world Haskell", the DOT was explained...</p>
  
  <pre><code>(f . g) x
  </code></pre>
  
  <p>...as just another syntax for...</p>
  
  <pre><code>f (g x) 
  </code></pre>
  
  <p>And in the code the guru sent, DOT was used from a foldr, with the "ins" function as the fold "collapse":</p>
  
  <pre><code>*Main&gt; let g=concatMap . ins
  *Main&gt; g 1 [[2,3]]
  [[1,2,3],[2,1,3],[2,3,1]]
  </code></pre>
  
  <p>OK, since I want to understand how the DOT is used by the guru, I try the equivalent expression according to the DOT definition, (f . g) x = f (g x) ...</p>
  
  <pre><code>*Main&gt; concatMap (ins 1 [[2,3]])
  
  &lt;interactive&gt;:1:11:
       Couldn't match expected type `a -&gt; [b]'
              against inferred type `[[[t]]]'
       In the first argument of `concatMap', namely `(ins 1 [[2, 3]])'
       In the expression: concatMap (ins 1 [[2, 3]])
       In the definition of `it': it = concatMap (ins 1 [[2, 3]])
  </code></pre>
  
  <p>What!?! Why?
  OK, I check concatMap's signature, and find that it needs a lambda and a list, but that's 
  just a human thinking; how does GHC cope? According to the definition of DOT above...</p>
  
  <pre><code>(f.g)x = f(g x), 
  </code></pre>
  
  <p>...what I did was valid, replace-wise:</p>
  
  <pre><code>(concatMap . ins) x y = concatMap (ins x y)
  </code></pre>
  
  <p>Scratching head...</p>
  
  <pre><code>*Main&gt; concatMap (ins 1) [[2,3]]
  [[1,2,3],[2,1,3],[2,3,1]]
  </code></pre>
  
  <p>So... The DOT explanation was apparently
  too simplistic... DOT must be somehow clever enough to understand
  that we in fact wanted "ins" to get curri-ed away and "eat" the first
  argument - thus becoming a function that only wants to operate on [t]
  (and "intersperse" them with '1' in all possible positions). </p>
  
  <p>But where was this specified? How did GHC knew to do this, when we invoked:</p>
  
  <pre><code>*Main&gt; (concatMap . ins) 1 [[2,3]]
  [[1,2,3],[2,1,3],[2,3,1]]
  </code></pre>
  
  <p>Did the "ins" signature somehow conveyed this... "eat my first argument" policy?</p>
  
  <pre><code>*Main&gt; :info ins
  ins :: t -&gt; [t] -&gt; [[t]]        -- Defined at b.hs:1:0-2
  </code></pre>
  
  <p>I don't see nothing special - "ins" is a function that takes a 't', 
  a list of 't', and proceeds to create a list with all "interspersals". Nothing about "eat your first argument and curry it away".</p>
  
  <p>So there... I am baffled. I understand (after an hour of looking at the code!) what goes on, but... God almighty... Perhaps GHC makes attempts to see how many arguments it can "peel off"?</p>
  
  <pre><code>  let's try with no argument "curried" into "ins",
    oh gosh, boom, 
    let's try with one argument "curried" into "ins",
    yep, works,
    that must be it, proceed)
  </code></pre>
  
  <p>Again - yikes...</p>
  
  <p>And since I am always comparing the languages I am learning with what I already know, how would "ins" look in Python? </p>
  
  <pre><code>a=[2,3]
  print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]
  
  [[1, 2, 3], [2, 1, 3], [2, 3, 1]]
  </code></pre>
  
  <p>Be honest, now... which is simpler?</p>
  
  <p>I mean, I know I am a newbie in Haskell, but I feel like an idiot... Looking at 4 lines of code for an hour, and ending up assuming that the compiler... tries various interpretations until it finds something that "clicks"?</p>
  
  <p>To quote from Lethal weapon, "I am too old for this"...</p>