Aplanar una lista de listas

Question

Tengo que escribir una función que aplana una lista de listas.

Por ejemplo flatten [] = [] o flatten [1,2,3,4] = [1,2,3,4] o flatten [[1,2],[3],4,5]] = [1,2,3,4,5]

Tengo problemas con el poder para que coincida con el tipo en función de lo que se da a la función aplanar.

Esto es lo que tengo:

data A a = B a | C [a] deriving (Show, Eq, Ord) 

flatten::(Show a, Eq a, Ord a)=>A a -> A a 
flatten (C []) = (C []) 
flatten (C (x:xs)) = (C flatten x) ++ (C flatten xs) 
flatten (B a) = (C [a]) 

De lo que puedo decir la cuestión es que el operador ++ está a la espera de una lista de sus dos argumentos y estoy tratando de darle algo de tipo A. Agregué el tipo A para que la función pueda obtener un solo elemento o una lista de elementos.

¿Alguien conoce una manera diferente de hacer esto de manera diferente, o explica qué puedo hacer para corregir el error de tipo?

Answer 1

No está nada claro qué está pidiendo, pero al alisar una lista de lista hay una función estándar llamada concat en el preludio con la firma de tipo [[a]] -> [a].

Si comete un tipo de datos de listas anidadas como haya comenzado anteriormente, tal vez usted quiere ajustar el tipo de datos a algo como esto:

data Lists a = List [a] | ListOfLists [Lists a] 

Entonces puede acoplar a una lista éstas;

flatten :: Lists a -> [a] 
flatten (List xs) = xs 
flatten (ListOfLists xss) = concatMap flatten xss 

Como prueba,

> flatten (ListOfLists [List [1,2],List [3],ListOfLists [List [4],List[5]]]) 
[1,2,3,4,5] 

Answer 2

En primer lugar, el tipo A está en el camino correcto, pero no creo que sea del todo correcto. Usted quiere que sea capaz de aplanar listas arbitrariamente anidadas, por lo que un valor de tipo "A un" debe ser capaz de contener valores de tipo "A un":

data A a = B a | C [A a] 

En segundo lugar, el tipo de la función debe ser ligeramente diferente. En lugar de devolver un valor de tipo "A a", probablemente desee devolver solo una lista de a, ya que por definición la función siempre devuelve una lista plana. Por lo que el tipo de firma es así:

flatten :: A a -> [a] 

También tenga en cuenta que no hay restricciones de clase de tipos son necesarios - esta función es totalmente genérico, ya que no toma en cuenta los elementos de la lista en absoluto.

Aquí está mi aplicación:

flatten (B a) = [a] 
flatten (C []) = [] 
flatten (C (x:xs)) = flatten x ++ flatten (C xs) 

Answer 3

éste forro hará el trabajo. Aunque como se mencionó por Malin del tipo de firma es diferente:

flatten :: [[a]] -> [a]   
flatten xs = (\z n -> foldr (\x y -> foldr z y x) n xs) (:) [] 

prueba simple

frege> li = [[3,4,2],[1,9,9],[5,8]] 
frege> flatten li 
[3,4,2,1,9,9,5,8]