Geek Answers Handbook

Function type creation depends on input

So, I noticed that after n = 20, the factorial function specified in LearnYouAHaskell (below) disappears due to the limited range of work of type Int.

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

Using factorial :: Integer -> Integer fixes the problem well, but this has drawn attention to the issue. Supposedly, Integer is a bit slower than Int, which is why it is perfect (and I know that I'm pinching a penny here). I would like my factorial function to use only Integer when input is greater than 20, and save the type Int->Int for smaller numbers. It seems like there should be an elegant solution for this using if-then-else or guard, but keep working in syntax pepper (error messages)

+6
source share
4 answers

You can make a hacker decision without dependent types, using the type of sum and increasing if necessary or delaying the cast to Integer to the end in some cases. I do not expect any solution to work better than using Integer - do not be afraid that Integer, gmp and mpir are not bad.

The casting solution is something like:

 selectiveFactorial :: Integer -> Integer selectiveFactorial i | i < 20 = fromIntegral $ factorial (fromIntegral i :: Int) | otherwise = factorial i factorial :: Integral a => a -> a factorial 0 = 1 factorial n = n * factorial (n - 1)
+11
source

As Rain Henriks said , you could do it in a language with dependent types, which Haskell does not have (yet, quite). In Idris, let's say it would look like

 factorial : (n : Int) -> if n <= 20 then Int else Integer factorial n with (n <= 20) factorial n | True = thisfactorial n factorial n | False = thatfactorial n

But how will you use this result? Well, you need to make a comparison to figure out what type to expect, and when everything is said and done, I don’t see how you won anything. For completeness, the usage site might look something like this:

 use : Int -> Integer use n with (factorial n) use n | fn with (n <= 20) use n | fn | False = fn use n | fn | True = cast fn

Please note that the order of with sentences is significant! The fn binding gets the type if n <= 20 then Int else Integer ; for reasons that I don’t quite understand, the test n <= 20 should be to the right of it so that a match with the pattern affects its type.

+7
source

It's impossible. There are things you can do:

  • Make the type more general: factorial :: Num a => a -> a ; This allows the user of your function to decide which punitive measures he wants to carry out, depending on which range of numbers is valid.

  • Use a sum type such as data PossiblyBig = Small Int | Big Integer data PossiblyBig = Small Int | Big Integer , and then have an implementation of instance Num PossiblyBig , which encodes things that fit in Int as Small , and things that don't fit as Big ; AFAIK Integer already works like this (look at the GMP implementation if you want to know for sure), so this is more of a general example than advice on what you should do in this particular situation.

+5
source

Setting the type of a function depends on its values, exactly for dependent types . Unfortunately, Haskell has no dependent types, so this cannot be done.

+1
source

More articles:


All Articles