algorithm - por - transposicion inversa

Cifrado de transposición de fila simple

Question

Para una clase Lisp, nos dieron una simple tarea de cifrado de transposición de fila, que también traté de resolver en Haskell. Básicamente, uno solo divide una cadena en filas de longitud n , y luego transpone el resultado. La concatenación de la lista resultante de listas de caracteres es la cadena cifrada. La decodificación es un poco más difícil, ya que pueden faltar elementos en la última fila de entrada (columnas incompletas en el resultado), que deben tenerse en cuenta.

Esta es mi solución en 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

Hace el trabajo, pero no estoy seguro, si esto se consideraría idiomático Haskell, ya que mi juego con los índices no parece demasiado declarativo. ¿Se podría mejorar esto, y si es así, cómo?

Por cierto: ¿hay algo parecido a insertAt en Haskell 98? Es decir, una función que inserta un elemento o lista en un índice dado en una lista.

Nota: Esto NO es parte de la tarea, que debía realizarse hoy de todos modos.

Answer 1

Haría esto mirando los problemas de encode y decode ligeramente diferente. encode divide los datos en una matriz de n columnas, que luego transpone (en una matriz n -row) y se concatena por filas. decode divide los datos en una matriz de n filas, que luego transpone (en una matriz de columnas n ) y se concatena por filas.

Así que comenzaría por definir dos funciones: una para hacer una matriz en una matriz de n columnas:

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

y otra para dividir una matriz en una matriz de n filas:

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

Ahora, la codificación y decodificación es bastante fácil:

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