Простой шифр транспонирования строк - PullRequest
Новая
       6

Простой шифр транспонирования строк

8 голосов
/ 20 декабря 2010

Для класса 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

Он выполняет свою работу, но я не уверен, будет ли это считаться идиоматическим Хаскеллом, так как моя игра с индексами не кажется слишком декларативной.Можно ли это улучшить, и если да, то как?

Кстати: есть ли что-то похожее на insertAt в Haskell 98?Т.е. функция, вставляющая элемент или список по заданному индексу в список.

Примечание. Это НЕ часть домашней работы, которая должна была быть выполнена сегодня.

1 Ответ

6 голосов
/ 20 декабря 2010

Я бы сделал это, посмотрев на проблемы 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
...