将列表转换为嵌套元组 Haskell

Question

将列表转换为嵌套元组 Haskell

3

简而言之，我的问题是我正在解析数字列表([Integer])，我想将该列表转换为嵌套元组，例如列表[1,2,3,4]将变为(1,(2,(3,4)))。我认为可以使用fold操作来实现。我遇到的问题是，在预先确定类型之前，元组嵌套可能会无限增长。

根据评论编辑

谢谢你们的回复，根本问题是一项任务，所以对于更大问题的细节很少，但为了不让你们疑惑，我可以稍微扩展一下，虽然我不需要扩展的答案。我的问题归结为上下文自由语法的右递归和右关联部分的问题，我有这样的东西

A -> n A

所以我可以得到这样的表达式'n n n n A'，它解析为'n(n(n(n A)))'(A还有其他终端)。我可以将其解析为'[n,n,n,n] A'，这就是我希望进行转换的原因(我知道有更好的方法，只是找不到)。

- dingo1337

9

这是因为类型取决于数据（完全依赖类型）。 - Thomas M. DuBuisson

谢谢你的回答，我也有这样的想法，但是还希望我可能忽略了什么。 - dingo1337

5

你可以定义自己的自定义类型 data T = Empty | Nonempty (Integer, T) 来表示元组的任意嵌套，但这样做只是给标准列表类型另起一个名字，所以没有什么好处。你为什么认为需要使用元组来处理数据？ - chi

1

另一种可能的编码方式：data NTup t = Here t | There (NTup (Integer,t))。然后，您可以使用NTup()来表示任意大小的嵌套元组。当您递归到Here时，t将是适当大小的嵌套元组（尝试使用show查看它）。这被称为非正则类型，在这种情况下我真的看不出做这件事的意义，但这是一个很好的技巧需要了解。 - luqui

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leftaroundabout · Accepted Answer

作为Thomas M. DuBuisson所评论的，以良好的方式实现这一点实际上是不可行的，因为列表长度仅在运行时已知，但不同深度的元组具有不同的类型，并且必须在编译时知道类型。

（严格来说，Haskell实际上能够使用Data.Dynamic类型作为完全动态类型的语言，但这种方法使用起来非常不实用。）

然而，如果您在编译时确实知道正确的深度，并且不匹配长度的列表应该是无效输入，则可以使用类似以下的内容，以实现一个合理的列表到元组转换：

{-# LANGUAGE FunctionalDependencies, FlexibleInstances #-}

class NestedTup e t where
  toNestedTup :: [e] -> Maybe t

instance NestedTup e e where
  toNestedTup [e] = Just e
  toNestedTup _ = Nothing
instance NestedTup h t => NestedTup h (h,t) where
  toNestedTup (h:t) = (h,)<$>toNestedTup t
  toNestedTup [] = Nothing

*Main> toNestedTup [1,2,3,4 :: Int] :: Maybe (Int,(Int,(Int,Int)))
Just (1,(2,(3,4)))
*Main> toNestedTup [1,2,3,4,5 :: Int] :: Maybe (Int,(Int,(Int,Int)))
Nothing