chiffrement de transposition de la ligne simple

Question

Pour une classe Lisp, on nous a donné un devoir simple chiffrement de transposition de la ligne, que j'ai essayé de résoudre en Haskell, aussi. En gros, on divise juste une chaîne en lignes de n de longueur, et le résultat transpose. La concaténation de la liste résultante des listes de caractères est la chaîne cryptée. Le décodage est un peu plus difficile, car il peut y avoir des éléments manquants dans la dernière ligne d'entrée (colonnes incomplètes dans le résultat), qui doivent être pris en charge.

Ceci est ma solution dans 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

Il fait le travail, mais je ne suis pas sûr, que cela serait considéré comme idiomatiques Haskell, depuis mon jongler avec les indices ne se sent pas trop déclaratif. Cela pourrait-il être amélioré, et si oui, comment?

A propos: Y at-il quelque chose de semblable à insertAt dans Haskell 98? C'est à dire. une fonction insertion d'un élément ou d'une liste à un index donné dans une liste.

Remarque:. Ce ne fait pas partie des devoirs, ce qui était dû aujourd'hui de toute façon

Answer 1

Je le faire en regardant les problèmes de encode et decode un peu différemment. pauses encode les données dans une matrice-colonne de n, qui transpose ensuite (dans une matrice de rangées n) et concatène par rangées. pauses decode les données en une matrice de rangées de n, qu'il transpose ensuite (dans une matrice de columm de n) et concatène par lignes.

Je voudrais commencer par définir deux fonctions - un pour faire un tableau dans une matrice de colonne 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

et l'autre pour trancher une matrice en une matrice de rangées de 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

Maintenant, encodage et le décodage est assez facile:

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