使用Haskell将随机嵌套的列表展平为非嵌套的列表 [英] Flatten randomly nested list into a non nested list using Haskell

问题描述

我有一个虚构的列表，具有不同级别的嵌套，或者忽略了API响应的丑陋类型，即:

I have an imaginary list with different levels of nesting, or ignoring the ugly types a API response ie:

a ::(Num a, Num [a], Num [[a]]) => [[a]]
a = [1, 2, [3, 4]]

b :: (Num a, Num [a], Num [[a]], Num [[[a]]]) => [[[[a]]]]
b = [[1,2,[3]],4]

我要创建的函数应该执行以下操作:

The function I'm trying to create should do the following:

myFunc a == [1,2,3,4]
myFunc b == [1,2,3,4]

我最初的想法是，我必须将列表解析为AST(抽象语法树).-->使用递归来展平所有分支&留在单个分支中-->将结果解析回列表中.

My initial thought was I'd have to parse the list into an AST (Abstract syntax tree) --> use recursion to flatten all the branches & leaves into a single branch --> parse the result back into a list.

我不确定如何将列表解析为AST?还是有更好的解决方案?

I'm unsure how to parse the list into AST? or is there a better solution?

edit-我想我太过直白了，因为代表[1, 2, [3, 4]]实际上是问题的一部分，因此，为了使事情更好地实际运行，它们必须被表示为ADT/AST.因此，如果这是API响应或正在读取文件，我如何将这些数据解析为AST/ADT?

edit -- I think I was trying to be too literal, in that representing [1, 2, [3, 4]] is actually part of the problem, so realistically for things to work better they would need to be represented as an ADT/AST. So if this was an API response or reading a file how would I parse that data into it's AST/ADT?

推荐答案

任意嵌套的列表将不会输入check.列表的每个元素必须具有相同的类型，但是具有不同嵌套级别的列表具有不同的类型.解决此问题的技巧是将列表包装成新的数据类型，以隐藏嵌套级别的数量.但这只是一棵树.

An arbitrarily nested list won't type check. Each element of a list has to have the same type, but lists with different nesting levels have different types. The trick to get around this is to wrap a list into a new data type that hides the number of nested levels. But this is just a tree.

data Tree a = Root a | Branches [Tree a]

然后，您可以实现flatten作为对树的遍历.

Then you can implement flatten as a traversal of the tree.

flatten :: Tree a -> [a]
flatten (Root a)          = [a]
flatten (Branches (t:ts)) = flatten t ++ (concat (fmap flatten ts))

有关可立即使用的版本，请参见容器包装中的Data.Tree.

See Data.Tree in the containers package for a ready-to-use version.

对于解析，我建议使用aeson. Data.Aeson.Types定义了实例FromJSON v => FromJSON (Tree v)，因此您应该只能够在json字符串上使用decode并告诉它您想要一个Tree Int.

For parsing, I would recommend using aeson. Data.Aeson.Types defines the instance FromJSON v => FromJSON (Tree v), so you should just be able to use decode on the json string and tell it you want a Tree Int.

decode rawJson :: Maybe (Tree Int)

这篇关于使用Haskell将随机嵌套的列表展平为非嵌套的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！