Simple row transposition cipher

Question

For a Lisp class, we were given a simple row transposition cipher homework, which I tried to solve in Haskell, too. Basically, one just splits a string into rows of length n, and then transposes the result. The concatenation of the resulting list of lists of chars is the encrypted string. Decoding is a little harder, since there may be missing elements in the last row of input (incomplete columns in the result), which have to be taken care of.

This is my solution in Haskell:

import Data.List
import Data.Ratio
import Data.List.Split

encode :: String -> Int -> String
encode s n = concat . transpose $ chunk n s

decode :: String -> Int -> String
decode s n = take len $ encode s' rows
    where s'     = foldr (insertAt " ") s idxs
          rows   = ceiling (len % n)
          idxs   = take (n-filled) [n*rows-1,(n-1)*rows-1..]
          filled = len - n * (rows - 1)
          len    = length s

insertAt :: [a] -> Int -> [a] -> [a]
insertAt xs i ys = pre ++ xs ++ post
    where (pre,post) = splitAt i ys

It does the job, but I am not sure, whether this would be considered idiomatic Haskell, since my fiddling with the indices does not feel too declarative. Could this be improved, and if yes, how?

By the way: Is there something akin to insertAt in Haskell 98? I.e. a function inserting an element or list at a given index into a list.

Note: This is NOT part of the homework, which was due today anyway.

Answer 1

I would do this by looking at the encode and decode problems slightly differently. encode breaks up the data into a n-column matrix, which it then transposes (into a n-row matrix) and concatenates by rows. decode breaks up the data into a n row matrix, which it then transposes (into a n columm matrix) and concatenates by rows.

So I'd start by defining two functions - one to make an array into an n column matrix:

chunk:: Int -> [a] -> [[a]]
chunk n as = chunk' n (length as) as
  where chunk' n l as | l <= n    = [as]
                      | otherwise = some : chunk' n (l-n) rest 
                          where (some, rest) = splitAt n as

and another to slice an array into an n row matrix:

slice :: Int -> [a] -> [[a]]
slice n as = chunk (q+1) front ++ chunk q back
  where (q,r) = length as `divMod` n
        (front, back) = splitAt (r*(q+1)) as

Now, encoding and decoding is fairly easy:

encode :: Int -> [a] -> [a]
encode = ((concat . transpose) .). chunk
decode :: Int -> [a] -> [a]
decode = ((concat . transpose) .). slice