algorithm - 简单的行转置密码

Question

对于 Lisp 类(class)，我们得到了一个简单的行转置密码作业，我也尝试用 Haskell 解决这个问题。基本上，只需将字符串拆分为长度为 n 的行，然后转置结果。字符列表的结果列表的串联是加密的字符串。解码有点困难，因为输入的最后一行中可能缺少元素(结果中的列不完整)，必须加以注意。

这是我在 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

它完成了工作，但我不确定，这是否会被视为惯用的 Haskell，因为我对索引的摆弄并不会让人觉得过于声明。这是否可以改进？如果可以，如何改进？

顺便问一下:Haskell 98 中是否有类似于 insertAt 的东西？ IE。将给定索引处的元素或列表插入列表的函数。

注意:这不是家庭作业的一部分，无论如何今天都要交。

Answer 1

我会通过查看 encode 来做到这一点和 decode问题略有不同。 encode将数据分解为 n -列矩阵，然后将其转置(转换为 n -行矩阵)并按行连接。 decode将数据分解为 n行矩阵，然后将其转置(转换为 n 列矩阵)并按行连接。

所以我首先定义两个函数 - 一个将数组变成 n列矩阵:

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

还有一个将数组切片为n行矩阵:

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

现在，编码和解码就相当容易了:

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