CODEWITHSUNDEEP
haskelllambda-calculus
HaskLearner9921
HaskLearner9921

Reputation: 43

How to write recursive factorial function in haskell without if then else statment

fac n = if n < 2 then 1 else n * fac (n-1)

main = do

   putStrLn "Enter a number: "  
   number <- getLine 
   print $ number >>= fac

I do not know how to write a recursive factorial function without if statements. Our professor said somethings about lambda calculus.

Upvotes: 3

Views: 4659

Answers (3)

wasmup
wasmup

Reputation: 16213

try this:

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

Using tail recursion:

factorial n = f n 1

f 0 acc = acc
f n acc = f (n-1) (acc*n)

main = print $ factorial 5

output:

120

Upvotes: 3

dfeuer
dfeuer

Reputation: 48580

If/then/else and guards are actually just syntactic sugar for pattern matching.

if b
  then c
  else d

desugars to

case b of
  True -> c
  False -> d

Similarly,

f x
  | b = c
  | d = e
f x = g

desugars to

f x = case b of
        True -> c
        False -> case d of
          True -> e
          False = g

So you can always use case directly. However, there's a rather simple optimization you can perform by hand. If you see

case x == p of
  True -> a
  False -> b

where p is made of constructors and literals, you can replace the whole thing with

case x of
  p -> a
  _ -> b

Upvotes: 1

Daniel Wagner
Daniel Wagner

Reputation: 152682

Pattern matching and guards are two particularly straightforward ways. Guards are essentially another syntax for if-then-else; they look like this:

fac n | n < 2     = 1
      | otherwise = n * fac (n-1)

Unlike if-then-else, they cleanly support multiple conditions; one could also write, for example,

fac n | n < 0 = error "nah"
      | n == 0 = 1
      | n == 1 = 1
      | n > 1 = n * fac (n-1)

which would look much less pretty in if-then-else form.

With pattern matching, one would typically write multiple defining equations:

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

For numbers in particular, this also desugars to essentially an if-then-else; but for data types with less compiler integration often cannot be emulated with if-then-else, and also often leads to very natural-looking code.

Another very nice approach would be to push your recursion into existing Prelude functions; the more you can spot iteration patterns in practice the more bugs you can avoid by not re-implementing the same loops over and over. For this one, you might use product and the special enumeration syntax:

fac n = product [1..n]

A more advanced (and significantly worse) technique would be to define a new kind of number; e.g. Church numerals allow the producer of the number to drive the recursion, and the consumer (here, fac) to just supply base cases. In this style, you might see something like this:

fac n = fst (n (1,1) (\(prod, sum) -> (prod*sum, sum+1)))

(But note well that this requires a very special kind of number -- certainly the type of fac is not one of a function that could accept Int or Integer!) This joke is taken to its logical and horrifying conclusion in The Evolution of a Haskell Programmer.

Upvotes: 7

Related Questions