CODEWITHSUNDEEP
haskellrecursiontypestuples
Ali
Ali

Reputation: 3

Ignore type declaration until last recursion

I'm trying to write a function which converts data in a tuple into a string for a program that does run length encoding. I've written it previously using append but I've been trying to improve it.

The function decode should take a list of tuples and then return a string.

Examples

> decode [('h',7),('s',3),('g',1)]
"hhhhhhhsssg"
> decode [('z',9),('z',1)]
"zzzzzzzzzz"

I initially wrote it recursively using the append function which works fine but isn't optimal, my current implementation looks this:

decode :: [(Char,Int)] -> String
decode [] = []
decode x = concat(replicate (snd (head x)) (fst (head x)) : decode (tail x)

This then gives me an error on compile as the decode (tail x) part doesn't fit the type declaration I'm not allowed to change. I'm sure it's bad practice but would there be a way to get the program not to conform to the type declaration until it finishes recursing?

    * Couldn't match type `Char' with `[Char]'
      Expected type: [[Char]]
        Actual type: String
    * In the second argument of `(:)', namely `decode (tail x)'
      In the first argument of `concat', namely
        `(replicate (snd (head x)) (fst (head x)) : decode (tail x))'
      In the expression:
        concat (replicate (snd (head x)) (fst (head x)) : decode (tail x))
   |
35 | decode x = concat(replicate (snd (head x)) (fst (head x)) : decode (tail x))
   |

Upvotes: 0

Views: 156

Answers (2)

Eduardo Hidalgo
Eduardo Hidalgo

Reputation: 131

The problem with your code is with the : cons function. it's type is a -> [a] -> [a] which means it puts a single element a list at the beginning. In your case you are trying to add a list (the replicated elements) to the list, that's why ++ works (it's type is [a] -> [a] -> [a]). There is no way to simply "ignore the type" because types are interleaved with how haskell compiles/runs, and that's a good thing, in this case the compiler saved you from a "type mismatch" runtime error in other langs.

if you want to write it with :, then you can't use replicate, you will need to make an auxiliary recursive function that repeats the char, and on zero decodes the rest of the list:

decodeA :: [(Char,Int)] -> String
decodeA [] = []
decodeA ((c,n):xs) = rep c n
           where rep ch 0 = decodeA xs
                 rep ch m = ch : (rep ch (m-1))

now a more clear solution arises from using ++:

decodeB :: [(Char,Int)] -> String
decodeB [] = []
decodeB ((c,n):xs) = replicate n c ++ decodeB xs

and benchmarking both solutions, the second is not only clearer but also faster:

benchmark code

t1 = [('h',7),('s',3),('g',1)]
t2 = [('z',9),('z',1)]
t3 = [('a',10000), ('b',10000), ('c',10000),('d',10000), ('e',10000), ('f',10000)]

main = defaultMain [
  bgroup "decode" [ bench "t1 decodeA" $ nf decodeA t1
                  , bench "t2 decodeA" $ nf decodeA t2
                  , bench "t3 decodeA" $ nf decodeA t3
                  , bench "t1 decodeB" $ nf decodeB t1
                  , bench "t2 decodeB" $ nf decodeB t2
                  , bench "t3 decodeB" $ nf decodeB t3
                   ]

benchmark results

benchmarking decode/t1 decodeA
time                 7.152 μs   (7.093 μs .. 7.225 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 7.129 μs   (7.091 μs .. 7.216 μs)
std dev              190.6 ns   (69.72 ns .. 354.5 ns)
variance introduced by outliers: 31% (moderately inflated)

benchmarking decode/t2 decodeA
time                 6.283 μs   (6.235 μs .. 6.340 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 6.268 μs   (6.239 μs .. 6.326 μs)
std dev              137.8 ns   (71.41 ns .. 211.7 ns)
variance introduced by outliers: 24% (moderately inflated)

benchmarking decode/t3 decodeA
time                 32.67 ms   (32.31 ms .. 33.08 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 32.68 ms   (32.53 ms .. 32.93 ms)
std dev              406.7 μs   (238.0 μs .. 613.5 μs)

benchmarking decode/t1 decodeB
time                 1.208 μs   (1.199 μs .. 1.220 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.212 μs   (1.204 μs .. 1.228 μs)
std dev              34.30 ns   (19.59 ns .. 62.18 ns)
variance introduced by outliers: 38% (moderately inflated)

benchmarking decode/t2 decodeB
time                 923.6 ns   (916.9 ns .. 931.6 ns)
                     0.999 R²   (0.997 R² .. 1.000 R²)
mean                 923.8 ns   (917.0 ns .. 950.3 ns)
std dev              38.01 ns   (9.440 ns .. 84.90 ns)
variance introduced by outliers: 57% (severely inflated)

benchmarking decode/t3 decodeB
time                 1.250 ms   (1.229 ms .. 1.274 ms)
                     0.997 R²   (0.995 R² .. 0.999 R²)
mean                 1.248 ms   (1.239 ms .. 1.269 ms)
std dev              47.55 μs   (32.05 μs .. 78.69 μs)
variance introduced by outliers: 26% (moderately inflated)

in this case, decodeB is 32 times faster than decodeA on the biggest test case

Upvotes: 4

Will Ness
Will Ness

Reputation: 71119

In Haskell we do not suppress errors, we fix them. The minimal edit(s) to fix the problem are:

decode :: [(Char,Int)] -> String
decode [] = []
decode x = -- concat(replicate (snd (head x)) (fst (head x)) : decode (tail x))  -- BAD
         =    concat[replicate (snd (head x)) (fst (head x)) , decode (tail x)]   -- OK
         =    concat(replicate (snd (head x)) (fst (head x)) : [decode (tail x)]) -- OK

Of course concat [a,b] == a ++ b, and thus

         =           replicate (snd (head x)) (fst (head x)) ++ decode (tail x)

i.e.

decode ((c,i):xs) =  replicate i c ++ decode xs

Thus, among many other possibilities suggested in the comments, 

decode :: [(Char,Int)] -> String
decode xs = [ c | (c,i) <- xs, _ <- [1..i]]

Upvotes: 2

Related Questions