Cifrado de transposición de fila simple

Question

Para una clase de Lisp, nos dieron una tarea simple 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 

Se hace el trabajo, pero no estoy seguro, si esto sería considerado idiomática Haskell, ya que mi jugando con los índices no se siente demasiado declarativa. ¿Se podría mejorar esto, y si es así, cómo?

Por cierto: ¿hay algo así como 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 se cumplió hoy de todos modos.

Answer 1

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

Así que me gustaría empezar por definir dos funciones - uno para hacer una matriz en una matriz n columna:

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 otro para cortar una matriz en una matriz n consecutivas:

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