有没有一个函数来扁平元素的嵌套列表?

我该如何扁平化一个嵌套列表:

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

由于没有人给出这个,所以可以通过使用MultiParamTypeClasses定义一个函数来平坦化任意深度的列表。 实际上我没有发现它有用,但希望它可以被认为是一个有趣的黑客。 我从Oleg的多variables函数实现中获得了这个想法。

 {-# LANGUAGE MultiParamTypeClasses, OverlappingInstances, FlexibleInstances #-} module Flatten where class Flatten io where flatten :: [i] -> [o] instance Flatten aa where flatten = id instance Flatten io => Flatten [i] o where flatten = concatMap flatten 

现在,如果你加载它并运行在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> :ti i :: [[[Integer]]] *Flatten> flatten i :: [Integer] [1,2,3,4,5,6] 

请注意,通常需要提供结果types注释,否则ghc无法确定recursion地应用flatten类方法的位置。 如果你使用一个单态types的函数就足够了。

 *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 

是的,这是从标准前奏, concat 给出

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

如果您想将[[[a]]]转换为[a] ,则必须使用两次:

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

正如其他人指出的那样, concat :: [[a]] -> [a]是您正在查找的函数,并且不能将任意深度的嵌套列表变平。 您需要多次调用才能将其平滑到所需的级别。

不过,这个操作确实会推广到其他monad。 它被称为join ,并且具有typesMonad m => m (ma) -> ma

 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 

正如哈马尔指出的那样, join是扁平化列表的“单子”方式。 您也可以使用do -Notation来轻松地编写几个级别的函数:

 flatten xsss = do xss <- xsss xs <- xss x <- xs return x 
 import Data.List let flatten = intercalate [] flatten $ flatten [[[1,2],[3]],[[4]]] [1,2,3,4] 

一个任意嵌套的列表可以用一个Data.Tree进行近似,这个Data.Tree可以用适当命名的函数flatten

我说近似,因为Data.Tree允许数据项被连接到每个节点,而不仅仅是叶子。 但是,您可以创build一个Data.Tree (Maybe a) ,并将Nothing到body节点,并使用catMaybes . flatten catMaybes . flatten

您可以使用concat删除一层嵌套,因此可以通过应用concat n次应用n层嵌套。

编写一个删除任意层次嵌套的函数是不可能的,因为不可能使用Haskell的types系统(使用列表数据types)来表示函数的types,该函数使用任意嵌套的列表并返回一个扁平列表那就是 – 你可以为自己的嵌套列表编写你自己的数据types,并为它写一个扁平函数)。