Haskell Integer and Int types; conversion not working

Question

I'm trying to solve Project Euler problem 59, where I have to xor-decrypt a message that has a three-character key (all lowercase). In ASCII this would mean the set of all keys is

let keys = [[a, b, c] | a <- [97..122], b <- [97..122], c <- [97..122]]

and the following functions would together heuristically decrypt it:

decrypt :: [Int] -> [Int] -> [Char]
decrypt msg xs = map chr $ zipWith xor msg $ (concat . repeat) xs

try :: [[Int]] -> [Int] -> [Char]
try kys msg = head $ filter (isInfixOf "the") $ map (decrypt msg) kys

where basically I keep on trying keys until one of them decrypts the message to have a "the" in it (I know the message has common English words). But when I bind keys and message and run try keys message I get

Couldn't match expected type `Int' with actual type `Integer'
    Expected type: [[Int]]
      Actual type: [[Integer]]
    In the first argument of `try', namely `keys'
    In the expression: try keys message

Now, even when I say let keys = [map fromIntegral [a, b, c] | a <- [97..122], b <- 97..122],, c <- [97..122]] it still says it has type Integer and not Int and also when I try let keys = map (map fromIntegral) keys, and also when I use fromInteger. What's going on?

hammar · Accepted Answer · 2012-10-20 21:04:43Z

4

The problem is that the type of keys defaults to [[Integer]]. Override this by adding a type annotation when defining keys:

let keys = ... :: [[Int]]

This is because the type of numeric literals (and the return type of fromIntegral) is polymorphic, so when you write let keys = ... the monomorphism restriction kicks in and defaults the numeric types to Integer unless they're constrained in some other way.

> let x = 42 
> :t x
x :: Integer
> let y = 42 :: Int
> :t y
y :: Int

Another solution is to disable the monomorphism restriction. Then keys will be a polymorphic value which will be specialized to [[Int]] when you try to use it.

> :set -XNoMonomorphismRestriction
> let x = 42
> :t x
x :: Num b => b

edited Oct 20, 2012 at 21:04

answered Oct 20, 2012 at 20:38

hammar

140k18 gold badges310 silver badges388 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

jclancy Over a year ago

If someone were to read this question in the future note that

let keys = [[a, b, c] | a <- map fromIntegral [97..122] :: [Int], b <- map fromIntegral [97..122] :: [Int], c <- map fromIntegral [97..122] :: [Int]]

was the precise code that fixed it. Also, thanks hammar, I wasn't aware of this form of typecasting.

Daniel Fischer Over a year ago

@jclancy If you specify a type of Int for (at least) one of the literals, or [Int] for (at least) one of the [97 .. 122] lists, or [[Int]] for keys, you don't need any fromIntegral.

jclancy Over a year ago

Ah, for some reason that didn't work for me before, maybe a typo. Then the best solution is let keys = [[a, b, c] | a <- [97..122], b <- [97..122], c <- [97..122]] :: [[Int]]

Collectives™ on Stack Overflow

Haskell Integer and Int types; conversion not working

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related