简单行置换密码

Question

对于一个Lisp课程，我们被分配了一个简单的行置换密码作业，我也尝试用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 的东西？也就是说，是否有一个函数将元素或列表插入到给定索引的列表中。

注意：这不是作业的一部分，而且作业今天已经截止。

- danlei

---

一个小提示：你可以写成 idxs = [n*rows-1,(n-1)*rows-1..(filled+1)*rows-1]。 - HaskellElephant

@HaskellElephant：看起来更好了，谢谢！ - danlei

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

- rampion

---

谢谢！小修正：在chunk'的第二个保护条件中应该是chunk'。 - danlei

(((concat . transpose) .). chunk) == (\x -> \y -> concat (transpose (chunk x y))) 等价于 \x -> \y -> concat (transpose (chunk x y))。 - ase

@adamse：是的。或许更易读的方式是：（.:）=（.）.（.），然后：（concat . transpose）.: chunk。 - danlei

在我看来，解读那段代码仍然有些困难。点无关风格确实很棒，但我认为这太过了。（可能是因为我对它不够熟悉） - ase

@adamse：在 ((concat . transpose) .) . slice 这种情况下，我认出了这个模式，因为我以前见过它（也就是当我学习 .: 时）。个人而言，我更喜欢点运算符版本，并且只在“明显”的情况下尝试使用无点风格，但我认为这相当主观（一种“品味”问题）。 - danlei

怎么样只写 encode x = concat . transpose . chunk x？ - HaskellElephant