list 是否有一个函数可以展平嵌套的元素列表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5994051/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a function to flatten a nested list of elements?
提问by Josh Lee
How can I flatten a nested list like this:
如何展平这样的嵌套列表：
[1, 2, 3, 4] == flatten [[[1,2],[3]],[[4]]]
采纳答案by John L
Since nobody else has given this, it is possible to define a function which will flatten lists of an arbitrary depth by using MultiParamTypeClasses. I haven't actually found it useful, but hopefully it could be considered an interesting hack. I got the idea from Oleg's polyvariadic function implementation.
由于没有其他人给出了这一点，因此可以定义一个函数，通过使用 MultiParamTypeClasses 来展平任意深度的列表。我实际上并没有发现它有用，但希望它可以被认为是一个有趣的黑客。我从 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
Now if you load it and run in ghci:
现在，如果您加载它并在 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]
Note that it's usually necessary to provide the result type annotation, because otherwise ghc can't figure out where to stop recursively applying the flattenclass method. If you use a function with a monomorphic type that's sufficient however.
请注意，通常需要提供结果类型注释，否则 ghc 无法确定在哪里停止递归应用flatten类方法。但是，如果您使用具有单态类型的函数就足够了。
*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
回答by Josh Lee
回答by hammar
As others have pointed out, concat :: [[a]] -> [a]is the function you are looking for, and it can't flatten nested lists of arbitrary depth. You need to call it multiple times to flatten it down to the desired level.
正如其他人指出的那样，concat :: [[a]] -> [a]是您正在寻找的功能，它不能展平任意深度的嵌套列表。您需要多次调用它才能将其压平到所需的水平。
The operation does generalize to other monads, though. It is then known as join, and has the type Monad m => m (m a) -> m a.
不过，该操作确实可以推广到其他 monad。然后它被称为join，并且具有类型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
回答by en4bz
import Data.List
let flatten = intercalate []
flatten $ flatten [[[1,2],[3]],[[4]]]
[1,2,3,4]
回答by Landei
As hammar pointed out, joinis the "monadic" way to flatten a list. You can use the do-Notation as well to write easily flatten functions of several levels:
正如 hammar 指出的那样，join是扁平化列表的“一元”方式。您也可以使用do-Notation 来轻松编写多个级别的扁平化函数：
flatten xsss = do xss <- xsss
xs <- xss
x <- xs
return x
回答by pat
An arbitrarily nested list can be approximated by a Data.Tree, which can be flattened by the appropriately named function flatten.
一个任意嵌套的列表可以近似为 a Data.Tree，它可以通过适当命名的函数展平flatten。
I say approximated because Data.Treeallows a data item to be attached to every node, not just the leaves. However, you could create a Data.Tree (Maybe a), and attach Nothingto the body nodes, and flatten with catMaybes . flatten.
我说近似是因为Data.Tree允许将数据项附加到每个节点，而不仅仅是叶子。但是，您可以创建一个Data.Tree (Maybe a), 并附Nothing加到主体节点，然后用 展平catMaybes . flatten。
回答by sepp2k
You can remove one level of nesting using concat, and consequently you can apply n levels of nesting by applying concatn times.
您可以使用 删除一层嵌套concat，因此您可以通过应用concatn 次来应用 n 级嵌套。
It is not possible to write a function which removes an arbitrary level of nestings, as it is not possible to express the type of a function, which takes an arbitrarily nested list and returns a flat list, using Haskell's type system (using the list datatype that is - you can write your own datatype for arbitrarily nested lists and write a flatten function for that).
不可能编写一个删除任意级别嵌套的函数，因为不可能表达函数的类型，该函数接受一个任意嵌套的列表并返回一个平面列表，使用 Haskell 的类型系统（使用列表数据类型也就是说 - 您可以为任意嵌套的列表编写自己的数据类型，并为此编写一个展平函数）。
