时间戳

首页 > 解决方案 > 在 Haskell 中展平任意深度的列表

haskell - 在 Haskell 中展平任意深度的列表

问题描述

我试图弄清楚如何在 Haskell 中展平一个任意深度的列表。现在我的功能看起来像：

data NestedList a = Regular [a] | Nested [NestedList a]

flatten::(Num a, Eq a)=> NestedList a -> [a]
flatten (Regular as) = as
flatten (Nested as) = concatMap flatten as

但后来我尝试调用它：

*Main> flatten [1,2,3,[1,[1,2]],2]

我收到此错误消息：

    • Couldn't match expected type ‘NestedList a’
                  with actual type ‘[[[Integer]]]’
    • In the first argument of ‘flatten’, namely
        ‘[1, 2, 3, [1, [1, 2]], ....]’
      In the expression: flatten [1, 2, 3, [1, [1, 2]], ....]
      In an equation for ‘it’: it = flatten [1, 2, 3, ....]
    • Relevant bindings include it :: [a] (bound at <interactive>:25:1)

我已经很久没有在 Haskell 中编程了，所以我真的不记得如何修复这个错误，或者我的函数是否完全错误。任何帮助，将不胜感激。

标签： haskell

解决方案

您没有构建一个嵌套列表，而是一个“简单”列表。此外，嵌套列表的定义实际上不允许编写您描述的列表，您可以将元素包装在单例列表中，但这会使它变得更加复杂。

您可以实现这样的嵌套列表：

data NestedList a = Leaf a | Nested [NestedList a]

如果您使用该-XDeriveFoldable选项，您甚至不需要flatten自己实现，但可以让 Haskell 为您完成工作：

{-# LANGUAGE DeriveFoldable #-}

data NestedList a = Leaf a | Nested [NestedList a] deriving Foldable

然后我们可以这样调用：

import Data.Foldable

toList (Nested [Leaf 1, Leaf 2, Leaf 3, Nested [Leaf 1,Nested [Leaf 1, Leaf 2]], Leaf 2])

对于给定的示例列表，这给了我们：

Prelude Data.Foldable> toList (Nested [Leaf 1, Leaf 2, Leaf 3, Nested [Leaf 1,Nested [Leaf 1, Leaf 2]], Leaf 2])
[1,2,3,1,1,2,2]

推荐阅读