Last active
December 7, 2019 02:03
-
-
Save kaveet/96ca4b81ba395bbd397013749f20717c to your computer and use it in GitHub Desktop.
Haskell Recursive Factorial Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- Compute the factorial of n recrusively | |
module Factorial where | |
factorial :: Int -> Int | |
factorial 0 = 1 | |
factorial n = n * factorial (n-1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The reason I didn't use
product
is because multiplication of twoNonnegative
integers is not guaranteed to bePositive
- that is,0
multiplied by anyNonnegative
will be0
(notPositive
). Therefore, we can't implement a function(*) :: Nonnegative -> Nonnegative -> Positive
and have it return a correct result (soproduct
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 that0
is the onlyNonnegative
number that is notPositive
(which might even be by definition), then the pattern matching onn
will be guaranteed to be a multiplication of twoPositive
integers (which will always give us aPositive
). Unfortunately, I think we need dependent typing for such a clean solution.If you want to convert a
Nonnegative
to aPositive
in Haskell (without a flag), you'll need to handle the case where0
is passed as input (which you can do withMaybe
). A function definition might looktoPositive :: 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.