How to pass function to itself as argument in Haskell

Question

In Python, I can write

fac = lambda slf, n: 1 if n == 0 else n * slf(slf, n - 1)
print(fac(fac, 4))  # prints 24

I'm trying to replicate it in Haskell. However, Haskell won't let me do this:

fac _ 0 = 1
fac slf n = n * slf slf (n - 1)

I'm getting this error:

    • Occurs check: cannot construct the infinite type: t ~ t -> p -> p
    • In the first argument of ‘slf’, namely ‘slf’
      In the second argument of ‘(*)’, namely ‘slf slf (n - 1)’
      In the expression: n * slf slf (n - 1)
    • Relevant bindings include
        n :: p (bound at app/Main.hs:9:10)
        slf :: t -> p -> p (bound at app/Main.hs:9:6)
        fac_ :: (t -> p -> p) -> p -> p (bound at app/Main.hs:8:1)
  |
9 | fac_ slf n = n * slf slf (n - 1)
  |                      ^^^

It seems the problem is that I'm not able to pass slf to slf. Is there a way to work around this? Thank you.

There is also Data.Function.fix, which lets you write fac = fix (\f x -> if x == 0 then 1 else x * f (x - 1)). I'm not quite up to writing a clear explanation of how this works, though it is similar to how Mu works. — chepner
– chepner, Commented Dec 19, 2021 at 14:56

Silvio Mayolo · Accepted Answer · 2021-12-19 01:56:00Z

You cannot directly do this. The type of every term in Haskell must be able to be written down, and the type of the term you're proposing would be infinite in length if written. The error message says as much: it says "I want to write the type of this, but it contains itself, so I stopped trying before blowing up your RAM".

However, Haskell does have recursive types. We use them every day, in the form of lists, trees, and any other structure that is self-similar. Haskell would never allow you to write a type Either () (Int, t), where t is Either () (Int, t). But that's exactly what [Int] is; it's just hidden behind a data constructor, so values of type [Int] can be infinitely long and self-similar (the tail of a list looks like a list), but the type is still written in the nice, neat, finite form [Int]. We can use the exact same trick to get a function which can be applied to itself.

newtype Mu a b = Mu { unMu :: Mu a b -> a -> b }

The type Mu a b is defined to contain a function which takes a Mu a b and an a and produces a b. We can now write a fac function which takes a Mu a a as argument.

fac :: (Num a, Eq a) => Mu a a -> a -> a
fac _ 0 = 1
fac slf n = n * unMu slf slf (n - 1)

and call it as

fac (Mu fac) 5

So we can never pass fac to itself as an argument. That will always produce an occurs check^[1]. But we can pass Mu fac, which has the nice, simple type Mu a a, as an argument to fac, which is an ordinary function. One layer of indirection, and you've got your recursive combinator.

You can use this same Mu trick to write the Y-combinator in its full, non-recursive glory. That's a valuable exercise in its own right that I highly recommend.

[1] It will always produce an occurs check on function types. It may be possible that you could do something truly insane with polymorphic recursion to make a function that can accept (a polymorphic variant of) itself as an argument, using something like the trick printf uses to get varargs in Haskell. This is left as an exercise to the reader.

amalloy · Accepted Answer · 2021-12-19 03:12:36Z

1

You can't do this in Haskell, for reasons Silvio Mayolo has explained. But, as in Python, you don't need to because you can give the function a name and have it call itself directly:

fac 0 = 1
fac n = n * fac (n - 1)

Just as in Python, this doesn't have to be a top-level function: you can define this function in a let binding and use it as you would any lambda.

answered Dec 19, 2021 at 3:12

amalloy

93k8 gold badges149 silver badges216 bronze badges

1 Comment

Leonid Over a year ago

I had the same question because I was reading a blog post about implementing Z combinator in Python and wanted to translate Python code into Haskell as an exercise: lptk.github.io/programming/2019/10/15/… I guess the question's author had similar reasons. In this context, telling that you don't really need to do it is not a helpful answer.

Collectives™ on Stack Overflow

How to pass function to itself as argument in Haskell

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related