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