Existe-t-il une fonction permettant d'aplatir une liste d'éléments imbriqués ?

Question

Comment puis-je aplatir une liste imbriquée comme celle-ci :

[1, 2, 3, 4] == flatten [[[1,2],[3]],[[4]]]

Answer 1

Oui, c'est concat du Prélude standard, donné par

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

Si vous voulez tourner [[[a]]] en [a] vous devez l'utiliser deux fois :

Prelude> (concat . concat) [[[1,2],[3]],[[4]]]
[1,2,3,4]

Answer 2

Puisque personne d'autre ne l'a fait, il est possible de définir une fonction qui aplatira des listes d'une profondeur arbitraire en utilisant les MultiParamTypeClasses. Je ne l'ai pas vraiment trouvé utile, mais j'espère que cela peut être considéré comme un hack intéressant. J'ai eu l'idée de l'implémentation de la fonction polyvariadique d'Oleg.

{-# LANGUAGE MultiParamTypeClasses, OverlappingInstances, FlexibleInstances #-}

module Flatten where

class Flatten i o where
  flatten :: [i] -> [o]

instance Flatten a a where
  flatten = id

instance Flatten i o => Flatten [i] o where 
  flatten = concatMap flatten

Maintenant si vous le chargez et l'exécutez en ghci :

*Flatten> let g = [1..5]
*Flatten> flatten g :: [Integer]
[1,2,3,4,5]
*Flatten> let h = [[1,2,3],[4,5]]
*Flatten> flatten h :: [Integer]
[1,2,3,4,5]
*Flatten> let i = [[[1,2],[3]],[],[[4,5],[6]]]
*Flatten> :t i
i :: [[[Integer]]]
*Flatten> flatten i :: [Integer]
[1,2,3,4,5,6]

Notez qu'il est généralement nécessaire de fournir l'annotation du type de résultat, parce que sinon ghc ne peut pas savoir où arrêter l'application récursive de la directive flatten méthode de classe. Si vous utilisez une fonction avec un type monomorphique, c'est suffisant.

*Flatten> :t sum
sum :: Num a => [a] -> a
*Flatten> sum $ flatten g

<interactive>:1:7:
    No instance for (Flatten Integer a0)
      arising from a use of `flatten'
    Possible fix: add an instance declaration for (Flatten Integer a0)
    In the second argument of `($)', namely `flatten g'
    In the expression: sum $ flatten g
    In an equation for `it': it = sum $ flatten g
*Flatten> let sumInt = sum :: [Integer] -> Integer
*Flatten> sumInt $ flatten g
15
*Flatten> sumInt $ flatten h
15

Answer 3

Comme d'autres l'ont souligné, concat :: [[a]] -> [a] est la fonction que vous recherchez, et elle ne peut pas aplatir des listes imbriquées de profondeur arbitraire. Vous devez l'appeler plusieurs fois pour l'aplatir au niveau souhaité.

L'opération se généralise cependant à d'autres monades. Elle est alors connue sous le nom de join et a le type Monad m => m (m a) -> m a .

Prelude Control.Monad> join [[1, 2], [3, 4]]
[1,2,3,4]    
Prelude Control.Monad> join (Just (Just 3))
Just 3
Prelude Control.Monad.Reader> join (+) 21
42

Answer 4

import Data.List
let flatten = intercalate []

flatten $ flatten [[[1,2],[3]],[[4]]]
[1,2,3,4]

Answer 5

Comme l'a souligné Hammar, join est la façon "monadique" d'aplatir une liste. Vous pouvez utiliser la fonction do -Notation également pour écrire facilement des fonctions aplaties de plusieurs niveaux :

flatten xsss = do xss <- xsss
                  xs <- xss
                  x <- xs
                  return x