title: Haskell "Apply"?
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/6168880/why-is-such-a-function-definition-not-allowed-in-haskell">Why is such a function definition not allowed in haskell?</a>  </p>
  </blockquote>
  
  
  
  <p>I'm a newcomer to the world of Haskell, migrating over from Lisp. I'm trying to adjust to Haskell's fundamentally different worldview, and one of the many things that I find new and exciting is the type system. Being a Lisper, I thought I would try to implement in Haskell a function which is very important in the Lisp world: <code>apply</code>. For those who don't know, apply takes a function and a list of arguments, and invokes the function on those arguments. In Scheme, <code>(apply + '(1 2 3))</code> is the same as invoking <code>(+ 1 2 3)</code>, and returns 6.</p>
  
  <p>My Haskell code looks something like this:</p>
  
  <pre><code>apply x [] = x
  apply f (x:xs) = apply (f x) xs
  </code></pre>
  
  <p>But Haskell complains:</p>
  
  <pre><code>ERROR line 2 - Type error in function binding
  *** Term           : apply
  *** Type           : (b -&gt; a) -&gt; [b] -&gt; a
  *** Does not match : a -&gt; [b] -&gt; a
  *** Because        : unification would give infinite type
  </code></pre>
  
  <p>And I think that I understand why. Apply's type needs to be different depending on the length of the list it is given. Given a list of, say, 3 items, apply's type would need to be: <code>(a -&gt; a -&gt; a -&gt; b) -&gt; [a] -&gt; b</code>, but given a list of 6 items, apply's type would need to be: <code>(a -&gt; a -&gt; a -&gt; a -&gt; a -&gt; a -&gt; b) -&gt; [a] -&gt; b</code>.</p>
  
  <p>I tried this horrendous work-around:</p>
  
  <pre><code>data FnOrDat a b = Dat b | Fn (a -&gt; FnOrDat a b)
  
  apply :: (FnOrDat a b) -&gt; [a] -&gt; (FnOrDat a b)
  apply x [] = x
  apply (Fn f) (x:xs) = apply (f x) xs
  apply (Dat _) _ = error "Cannot apply something which is not a function!"
  
  add a = Fn (\b -&gt; Dat (a + b))
  
  main = putStrLn $ show $ x where Dat x = apply (Fn add) [5,1]
  </code></pre>
  
  <p>This works, but it hardly counts as an <code>apply</code> function, because I can't pass <code>apply</code> a normal function, I have to use one that has been written specifically to use my (awkward) FnOrDat abstraction. If I wanted to write a function that added four numbers, I would need to write</p>
  
  <pre><code>add4 a = Fn (\b -&gt; Fn (\c -&gt; Fn (\d -&gt; Dat (a + b + c + d))))
  </code></pre>
  
  <p>Ew.</p>
  
  <p>So - am I missing something, or is asking for a general-purpose <code>apply</code> basically like asking for a function that can manipulate an arbitrary-length tuple? Does <code>apply</code> even make sense in the statically-typed worldview of Haskell?</p>