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.
You have to pass file1 etc. to runQuery like every other function argument: main = do (file1:file2:file3:_) <- getArgs checkdata command <- getLine runQuery file1 file2 file3 (words command) runQuery file1 file2 file3 ("queryname":parameter1:parameter2) = do ... Well that was simple.
The ++ operator is the list concatenation operator which takes two lists as operands and "combines" them into a single list.
[negate is the function applied by Haskell's only prefix operator, minus; we can't call it (-), because that is the subtraction function, so this name is provided instead. For example, -x*y is equivalent to negate (x*y).
No, Haskell is not pass-by-reference. Nor is it pass-by-value. Pass-by-reference and pass-by-value are both strict evaluation strategies, but Haskell is non-strict.
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With