3

Assume

f x y z = x*y*z

Then I expect to return the application of f three times with each member of the list

foldl ($) f [1,2,3]

Something like (((f 1) 2) 3) = 1*2*3 = 6

The function f would be the accumulator and each iteration of the fold would apply one argument and return a partially applied function as the next accumulator.

Why doesn't this work? Is it because f changes type while iterating?

As an aside: is there any other way to accomplish this type of function application?

Juan Pablo Santos
  • 1,200
  • 2
  • 10
  • 25
  • 1
    possible duplicate of [How do I define Lisp’s apply in Haskell?](http://stackoverflow.com/questions/6168880/how-do-i-define-lisp-s-apply-in-haskell) – Ganesh Sittampalam Jul 08 '14 at 18:54
  • 5
    As a really trivial counterexample, consider `foldl ($) f [1,2,3,4]`. It's clearly wrong, so if you want `foldl ($) f [1,2,3]` to typecheck and `foldl ($) f [1,2,3,4]` to not then you need to find some way to distinguish `[1,2,3]` and `[1,2,3,4]` in types. This doesn't happen with plain lists, and [once you do this you can write the function you desire.](http://hackage.haskell.org/package/fixed-vector) – J. Abrahamson Jul 08 '14 at 19:00
  • I believe this question is much more specific than the general Lisp apply. – Juan Pablo Santos Jul 08 '14 at 19:01
  • 1
    Then I'm not sure what you're asking. Do you want to know (a) why `foldl ($) f [1,2,3]` doesn't typecheck in Haskell as it stands, (b) can Haskell be changed to make it type-check, (c) what different expression can be written in current Haskell instead that would type-check or (d) something else ? – Ganesh Sittampalam Jul 08 '14 at 19:06
  • 1
    As for Scheme's `apply`, I have heard Scheme experts complain bitterly about its existence. It apparently makes good compilation rather more difficult. Scheme long ago gutted its `eval` for this same reason, and I think the implementors would probably love to nix `apply` altogether. – dfeuer Jul 08 '14 at 19:15

2 Answers2

6

The types look like

foldl :: (a -> b -> a) -> a -> [b] -> a

($) :: (x -> y) -> x -> y

To apply foldl to ($) requires matching (technically, unifying) the type of the first argument to foldl with the type of ($). That is, solving the equation

a -> b -> a  =  (x -> y) -> x -> y

This leads immediately to

a = x -> y
b = x
a = y

Substituting the second and third equations into the first:

a = b -> a

The problem is that Haskell has no type that solves this equation. In particular, it is impossible to write down a solution with a finite number of symbols! It expands first to

a = b -> b -> a

then

a = b -> b -> b -> a

and on forever. So there is no way to choose types for the type variables to make them match, and GHC will complain loudly.

dfeuer
  • 48,079
  • 5
  • 63
  • 167
3

In general, you can't do what you're trying to do because the type system distinguishes between functions with different numbers of arguments. What you're trying to do, essentially, is convert a list of values into a list of arguments for a function, which doesn't make sense in context.

However, the instance you're pointing at is literally just foldl (*). If you're performing the same operation on all of the variables in a function, you can just use this (well, you should be using either foldl' or foldr, but you get the idea).

Benjamin Kovach
  • 3,190
  • 1
  • 24
  • 38