How to pass function to itself as argument in Haskell-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

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.