8

对于 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，因为我对索引的摆弄并不会感觉过于声明性。这可以改进吗？如果可以，如何改进？

insertAt顺便说一句： Haskell 98 中是否有类似的东西？即将给定索引处的元素或列表插入列表的函数。

注意：这不是家庭作业的一部分，无论如何，这都是今天到期的。

4

1 回答 1

6

我会通过稍微不同地 看待encode和问题来做到这一点。将数据分解为-column矩阵，然后将其转置（成-row 矩阵）并按行连接。 将数据分解为行矩阵，然后将其转置（转换为列矩阵）并按行连接。decodeencodenndecodenn

所以我首先定义两个函数 - 一个将数组变成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
于 2010-12-20T19:10:54.057 回答