20

Possible Duplicate:
Why is such a function definition not allowed in haskell?

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: apply. For those who don't know, apply takes a function and a list of arguments, and invokes the function on those arguments. In Scheme, (apply + '(1 2 3)) is the same as invoking (+ 1 2 3), and returns 6.

My Haskell code looks something like this:

apply x [] = x
apply f (x:xs) = apply (f x) xs

But Haskell complains:

ERROR line 2 - Type error in function binding
*** Term           : apply
*** Type           : (b -> a) -> [b] -> a
*** Does not match : a -> [b] -> a
*** Because        : unification would give infinite type

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: (a -> a -> a -> b) -> [a] -> b, but given a list of 6 items, apply's type would need to be: (a -> a -> a -> a -> a -> a -> b) -> [a] -> b.

I tried this horrendous work-around:

data FnOrDat a b = Dat b | Fn (a -> FnOrDat a b)

apply :: (FnOrDat a b) -> [a] -> (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 -> Dat (a + b))

main = putStrLn $ show $ x where Dat x = apply (Fn add) [5,1]

This works, but it hardly counts as an apply function, because I can't pass apply 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

add4 a = Fn (\b -> Fn (\c -> Fn (\d -> Dat (a + b + c + d))))

Ew.

So - am I missing something, or is asking for a general-purpose apply basically like asking for a function that can manipulate an arbitrary-length tuple? Does apply even make sense in the statically-typed worldview of Haskell?

Community
  • 1
  • 1
Ord
  • 5,693
  • 5
  • 28
  • 42

3 Answers3

11

apply isn't very useful in Haskell, since you can't give a type to the function. As you see in your FnOrDat, you're essentially embedding a Lisp language into Haskell as an EDSL to force something through.

asking for a general-purpose apply basically like asking for a function that can manipulate an arbitrary-length tuple?

Exactly. You can come up with type class instances for certain useful combinations of types, but there's just not really a need or use for a general variadic apply.

As a side note, you should consider upgrading to GHC and the Haskell Platform, instead of the obsolete Hugs system, since you're missing out on most of libraries, tools and language features developed in the last 10 years.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • 2
    Thanks! Actually, I do use GHC on my "main" computer. I'm typing this up somewhere else though, so I just used codepad.org to test my code snippets. I guess they use Hugs? – Ord May 26 '12 at 15:26
  • @Ord they do use hugs, with the `-98` flag. See http://codepad.org/about – Dan Burton May 26 '12 at 19:08
4

Notwithstanding Don's explanation, foldl1 (+) would actually add all elements of a list. Hence, one could say that the fold family of functions comes quite close to the apply as the OP describes it.

Ingo
  • 36,037
  • 5
  • 53
  • 100
  • 1
    Yes, for certain types of functions I guess. But if you had a function like `discriminant a b c = b*b - 4*a*c`, in Lisp you'd be able to say `(apply discriminant '(2 3 4))`. You can't do this with fold. – Ord May 26 '12 at 15:39
  • 7
    On the other hand, I don't know why apply would ever be used like this. In Lisp, you usually use apply when you have a function that accepts any number of arguments, and this concept doesn't carry over to Haskell. – Ord May 26 '12 at 15:41
  • 1
    Well, yes, but then `apply3 f (a:b:c:_) = f a b c` is a one liner. – Ingo May 26 '12 at 15:43
  • 6
    You can play games with currying though, to reflect arity into nested tuples, `uncurry ( uncurry discriminant ) ((2,3),4) ==> -23` . It's just not a Haskell thing to do. – Don Stewart May 26 '12 at 15:44
  • @DonStewart Cool! I'd never heard of `uncurry` before. But yes, I see why it isn't really a common Haskell idiom. – Ord May 26 '12 at 15:45
1

... a function which is very important in the Lisp world: apply. For those who don't know, apply takes a function and a list of arguments, and invokes the function on those arguments. In Scheme, (apply + '(1 2 3)) is the same as invoking (+ 1 2 3), and returns 6. ...

This is quite simple:

foldr  (+) 0 [1,2,3]
foldr1 (+)   [1,2,3]

results in 6.

To apply a function to each element of a list:

map f list

e.g.

map (2*) [1,2,3]

results in [2,4,6]

Is this what you are looking for?

jimmyt
  • 491
  • 4
  • 10
  • 2
    Not quite. If you define `discriminant a b c = b*b - 4*a*c`, in Lisp you'd be able to say `(apply discriminant '(2 3 4))`. Another (more useful) example: in Lisp, the map function can take any number of list arguments. Not only can I say `(map square '(1 2 3 4)) -> '(1 4 9 16)`, but I can say `(map + '(1 2 3) '(4 5 6)) -> '(5 7 9)` (which is like zipWith), or `(map * '(1 2 3) '(3 2 1) '(0 2 0)) -> '(0 8 0)`. If I have a list of lists, x, I'd be able to say `(apply map + x)` to get the term-wise sum of the lists. You can't do any of these things with fold. – Ord May 28 '12 at 21:28