0

So, I have no idea how to formally call this question, but I want to know why my Haskell implementation (Haskell Platform, ghci) can't produce functions like this:

reverse.(foldr (:))

I would expect it to be of the type [a] -> [a] -> [a], just as foldr (:) is.

Now, after all,

reverse.(foldr (:) [])

is of type [a] -> [a], just as foldr (:) [] is, so there seems to be some problem with abstracting away two arguments.

Is there a compiler/interpreter flag to have it approach this sufficiently naively, or is what I am trying to do just plainly ambiguous?

Leif Willerts
  • 205
  • 1
  • 9
  • 2
    You might want to add spaces around `.`, I was really confused why you thought `reverse (foldr (:))` would type check. – Reid Barton Sep 02 '15 at 14:36
  • It's not ambiguous, it's just not type correct. Substituting in the definition `f . g = \x -> f (g x)` we get: `\x -> reverse ((foldr (:)) x)`, which is the same as `\x -> reverse (foldr (:) x)`. This doesn't type check because `foldr (:) x` is a function and `reverse` expects a list. There is a detailed explanation of this particular example [here](http://stackoverflow.com/a/32357030/2476735). – David Young Sep 02 '15 at 15:58
  • Notice that in Haskell `f :: a -> b -> c` means literally `f :: a -> (b -> c)`, it takes one argument and returns a function. This is distinct from `uncurry f :: (a, b) -> c` which takes both parameters in one argument (a pair) up-front. In particular `(. f) :: ((b -> c) -> z) -> a -> z` expects its first argument (which gets put in before the `.`) to take that "output" `b -> c` and turn it into something else, as distinct from `(. uncurry f) :: (c -> z) -> (a, b) -> z`, which is what you were expecting. So `curry (reverse . uncurry (foldr (:))` does what you want, albeit not idiomatically. – CR Drost Sep 02 '15 at 21:06
  • The more idiomatic solution would be to "lift" reverse into something which indeed is a `(b -> c) -> z`, in this case by replacing it with `(reverse .) :: (a -> [b]) -> a -> [b]`, propagating the dependence on the argument. `(reverse .) . foldr (:) :: [a] -> [a] -> [a]` type-checks just fine. Your first argument , say `p`, comes into this and produces `reverse . (foldr (:) p)` by the usual rules of `.`, then your next argument `q` comes in to make this `reverse (foldr (:) p q)`. Side note: `foldr (:)` is probably going to be more obvious if written as `flip (++)`. – CR Drost Sep 02 '15 at 21:15

0 Answers0