En Haskell, concat construye una lista perezosamente pero mi propia versión con un giro, no lo hace

Question

Estoy tratando de hacer una función relativamente simple que es casi concat pero con un pequeño giro. Se supone que es binario o juntos los últimos y primeros elementos de cada lista y los combina en el proceso. Estoy trabajando para aprender a escribir código que puede aprovechar las capacidades de Stream Fusion en Data.List.Stream

Comprobé que el concat en base hace lo que se necesita y construye la lista perezosamente, sin embargo, esta versión I creado no. en la base, concat se especifica de la siguiente manera:

concat :: [[a]] -> [a] 
concat = foldr (++) [] 

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

Aquí está mi código:

bconcat :: [[Word8]] -> [Word8] 
bconcat = foldr1 bappend 

bappend :: [Word8] -> [Word8] -> [Word8] 
bappend as bs = init as ++ (last as .|. head bs) : tail bs 

La pregunta que tengo es, ¿Cómo escribo esto para que la lista se construye con pereza? Incluso traté de escribir al pasar imitando la definición (++) en la base, pero no hizo la diferencia.

Por el momento, uso el siguiente código, funciona de la manera que quiero, pero el rendimiento se queda atrás concat. Además, utiliza la recursión explícita que me gustaría evitar.

bconcat :: [[Word8]] -> [Word8] 
bconcat (a:b:xs) = init a ++ bconcat ((bappend (last a) b):xs) 
bconcat (a:[]) = a 
bconcat [] = [] 

bappend :: Word8 -> [Word8] -> [Word8] 
bappend !a bs = (a .|. head bs) : tail bs 

Por lo tanto, la pregunta que tengo es, ¿Cómo se escribe el código por lo que construye la lista con pereza y sin recursión explícita?

Gracias por su tiempo.

Editar:

Mi principal interés, por el momento, está haciendo un código limpio, conciso y understable con los combinadores estándar. Todavía soy un principiante con un pensamiento funcional y me encantaría ver una forma razonablemente eficiente de ponerlos en práctica aquí.

Answer 1

Tu definición me parece estricta. Por ejemplo, intente evaluar

length $ bconcat [[1,2,3],[4,undefined,6]] 

Pero podría estar acumulando errores para el. |. expresión. Quizás quieras forzar eso.

Siempre se puede fusionar cosas por uno mismo si no lo hacen así fusible automáticamente:

bconcat [] = error "bconcat: empty outer list" 
bconcat (xs:xss) = loop xss xs 
    where loop [] ys = ys 
     loop ((x:xs):xss) [y] = let z = x .|. y in seq z $ z : loop xss xs 
     loop ([]:_) _ = error "bconcat: empty inner list" 
     loop xss (y:ys) = y : loop xss ys 

Answer 2

Parece que tiene un error tipográfico, 'bapennd' debe ser 'bappend' en el primer fragmento. Y creo que 'combinar' en el último fragmento debería ser 'bconcat'.

Parece que el primero (foldr1 bappend) será bastante vago. ¿Podría explicar la falta de pereza?

En cuanto a la necesidad tanto "init x" y "últimos XS", al mismo tiempo, es posible que desee un solo recorrido de xs:

let un [] = error "no last element" 
    un (x:[]) = ([],x) 
    un (x:xs) = let (ys,z) = un xs 
       in (x:ys,z) 

Esto tiene un espacio y tiempo disyuntiva diferente. Si siempre fuerza la respuesta de bconcat en orden, entonces es probable que sea una mejora. El "último x" contiene una referencia al encabezado de la lista completa y evita que xs se recolecte como basura hasta que se fuerce.

Answer 3

puedo cambiar la respuesta por augustuss para que coincida más de cerca el problema original de la escritura:

bconcat2 [] = [] 
bconcat2 (xs:xss) = loop xss xs 
    where loop [] ys = ys 
     loop xss (y:[]) = gather xss y 
     loop xss (y:ys) = y : loop xss ys 
     loop (xs:xss) [] = loop xss xs 
     gather [] z = [z] 
     gather ([]:xss) z = gather xss z 
     gather ((x:[]):xss) z = gather xss $! z .|. x 
     gather ((x:xs):xss) z = let z' = z .|. x in z' : loop xss xs 

Lo anterior ignora cualquier lista interna vacía.