Haskell Recursive Factorial Implementation

factorial.hs

-- Compute the factorial of n recrusively

module Factorial where

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

@Muttsuri I see that I'm a bit late here but I want to answer in case anyone else comes across this page.

Firstly, your solution with product is, to me, the preferred implementation (of any on this page). It's clear and concise. However, the original gist is fine as a mental exercise for defining a simple recursive function.

In regards to handling negative integers, let's first consider what it means to take the factorial of a negative integer. In mathematics, the factorial of a negative integer is undefined, which means it doesn't really make sense to say factorial (-1) in the first place.

An easy way to handle this in Haskell is with the Maybe monad. This is like saying, "If you give me a negative number, I won't even give you an Int! For any other number, I'll compute the factorial."

factorial :: Int -> Maybe Int
factorial n
  | n < 0     = Nothing
  | otherwise = Just $ product [1..n]

But there's actually an even better way. Consider that we can be a little more careful with our types here. The mathematical factorial takes, as input, a non-negative integer (zero or a positive integer) and returns, as output, a positive integer. If we had previously defined adequate types, we might get a function like this:

factorial :: Nonnegative -> Positive
factorial 0 = 1
factorial n = n * factorial (n-1)

With such a definition, the compiler won't even accept a number that's less than 0 as input! In this way, we've truly made factorial as close to the mathematical definition as possible. Of course, I've brushed over how we can define those types, but if you're interested in something like this, then you can look into what are called dependent types.

Hope that helps!

Funny enough I'm now at a point where I understand what a basic type class is so that I can understand what you mean.
For dependent typing in Haskell it seems you have to turn on a flag (personally I want to get solid on the basis before I start using flags).<

I wonder however if this could be done with just the normal non dependent type classes that Haskell offers.
And I assume you are using the pattern matching instead of the product because if so you would have to define how Nonnegative and Positive behave for lists right ?

And I assume you are using the pattern matching instead of the product because if so you would have to define how Nonnegative and Positive behave for lists right ?

The reason I didn't use product is because multiplication of two Nonnegative integers is not guaranteed to be Positive - that is, 0 multiplied by any Nonnegative will be 0 (not Positive). Therefore, we can't implement a function (*) :: Nonnegative -> Nonnegative -> Positive and have it return a correct result (so product won't work here since it uses (*) in its implementation).

In the version with pattern matching, we use the 0 case as the base case. If we have a proof that 0 is the only Nonnegative number that is not Positive (which might even be by definition), then the pattern matching on n will be guaranteed to be a multiplication of two Positive integers (which will always give us a Positive). Unfortunately, I think we need dependent typing for such a clean solution.

If you want to convert a Nonnegative to a Positive in Haskell (without a flag), you'll need to handle the case where 0 is passed as input (which you can do with Maybe). A function definition might look toPositive :: Nonnegative -> Maybe Positive. So yes, it's definitely possible.

Just to be clear, this doesn't have anything to do with how the types behave for lists. Since a list is a monad, it can "wrap" any type.