Haskell couldn't match expected type with actual type

Question

So I'm trying to use frequency analysis to decipher a code.

import Data.Char
import Data.List
import Data.Function
import qualified Data.Map as DMap

codedMsg    = "V'Z GELVAT GB GRNPU GUR PNIRZRA GB CYNL FPENOOYR. VG'F HCUVYY JBEX. GUR BAYL JBEQ GURL XABJ VF 'HAU', NAQ GURL QBA'G XABJ UBJ GB FCRYY VG."

mostFreqLtr = ["E", "T", "A", "O", "I", "N", "S", "H", "R", "D", "L", "C", "U", "M", "W", "F", "G", "Y", "P", "B", "V", "K", "X", "J", "Q", "Z"]

--weed out non alphabetical characters from the list
alphaSort lst
    | null lst              = []
    | isAlpha (head lst)    = (head lst) : alphaSort (tail lst)
    | otherwise             = alphaSort (tail lst)

--sort the list by characters
msgSort []  = []
msgSort lst = sortBy (compare `on` ord) lst

--group each character into it's own list
grp []  = []
grp lst = group lst

--sort the list into most frequent character first
lSort []    = []
lSort lst   = reverse (sortBy (compare `on` length) lst)

--change the list into one instance of each character
oneChar []  = []
oneChar lst = take 1 (head lst) : oneChar (tail lst)

--Pairing letters and creating a map of tuples containing frequency related characters
msg     = zip (oneChar $ lSort $ grp $ msgSort $ alphaSort $ map toUpper $ codedMsg) mostFreqLtr
msg2    = DMap.fromList msg

--replace coded list with analyzed list
replaceChars lst
    | null lst              = []
    | isAlpha (head lst)    = DMap.lookup (head lst) msg2 : replaceChars (tail lst)
    | otherwise             = (head lst) : replaceChars (tail lst)

result = replaceChars codedMsg

I keep getting this error:

Couldn't match expected type `Char' with actual type `[Char]'
    Expected type: DMap.Map Char a0
      Actual type: DMap.Map [Char] [Char]
    In the second argument of `DMap.lookup', namely `msg2'
    In the first argument of `(:)', namely
      `DMap.lookup (head lst) msg2'

Answer 1

Write type signatures on all your top-level functions. Then you will find that

oneChar :: [[a]] -> [[a]]

while, from the use, I surmise you intended

oneChar :: [[Char]] -> [Char]

Instead of take 1, you should have used head, or you should've concated the result to obtain a list of Chars.

As is, the map msg2 that you construct has [Char] as keys, but you try to use it as if it had Chars as keys.

Answer 2

hmm - I sat down and thought a bit about your code

• please use type signatures it helps a lot thinking about your code - and the compiler can optimize too

• give names that are a bit more meaningful

  • mostFreqLtr -> freqTable_EN (it makes clear you're deciphering English text)
  • alphaSort -> filterAlpha (it is misleading as you're filtering non letter elements and not sorting anything
  • msgSort -> sort (as it is the same i think)
• use pattern matching rather than head and tail
  i.e. lst ... head lst ... tail lst -> lst@(c:cs)
  • lst then is referrable as itself and c is its head and cs its tails (single elements are often referred as single letters, lists as their quasiplurals with appended s

Code:

import Prelude hiding (lookup)
import Data.Char ( isAlpha
                 , toUpper)
import Data.List ( group
                 , sort
                 , sortBy)
import Data.Function (on)
import Data.Map ( fromList
                , lookup
                , Map)
import Data.Maybe (mapMaybe)

only import necessary bits of code

codedMsg :: String
codedMsg    = "V'Z GELVAT GB GRNPU GUR PNIRZRA GB CYNL FPENOOYR." ++ 
              "VG'F HCUVYY JBEX. GUR BAYL JBEQ GURL XABJ VF 'HAU'," ++
              "NAQ GURL QBA'G XABJ UBJ GB FCRYY VG."

freqTable_EN :: [Char]
freqTable_EN = ['E', 'T', 'A', 'O', 'I', 'N', 'S', 'H', 'R'] ++
               ['D', 'L', 'C', 'U', 'M', 'W', 'F', 'G', 'Y'] ++
               ['P', 'B', 'V', 'K', 'X', 'J', 'Q', 'Z']

do not use too long lines - it makes code less readable, the last name freqTable_EN is quite unusual but in this case I feel free to deviate from standard as it is better readable. I also use [Char] instead of String (which is equivalent) to make it more clear that it is a table of letters.

-- weed out non alphabetical characters from the list
filterAlpha :: String -> String
filterAlpha = filter isAlpha

-- sort a list by length
sortByLength :: [[a]] -> [[a]]
sortByLength = sortBy (compare `on` length)

-- sort the list into most frequent character first
sortByFreq :: [[a]] -> [[a]]
sortByFreq = reverse . sortByLength

such comments are not necessary with good function names

-- change the list into one instance of each character
reduceGroups :: [[a]] -> [a]
reduceGroups lst = map head lst

you can also leave the lst thing the compiler is smart enough to get all information from the type signature so the last line could also be reduceGroups = map head

-- Pairing coded message with frequency table
pairs :: [(Char, Char)]
pairs = nonAlphaPairs ++ zip freqSortedMsg freqTable_EN
  where cleanedMsg    = (filterAlpha . map toUpper) codedMsg
        freqSortedMsg = (reduceGroups . sortByFreq . group . sort) cleanedMsg
        nonAlphaPairs = map (\x ->(x,x)) $ filter (not . isAlpha) codedMsg

(\x -> (x,x)) is a lambda expression it simply transforms a single character in a pair as they're deciphered by themselves

-- and creating a map for decryption
cipher :: Map Char Char
cipher = fromList pairs

-- replace encoded text by our cipher
decipher :: String -> String
decipher = mapMaybe (uplook cipher)
         where uplook = flip lookup

result :: String
result = decipher codedMsg

main :: IO ()
main = print result

the last line makes your result printed - as we want to read the message ;-) Feel free to ask if something is unclear.

PS.: I really like your coded message - though not even one letter is found by frequency analysis. I just guessed your ciphering algorithm. (g? for vim users), I think you have to use a longer text.