2

在几种编程语言（包括 JavaScript、Python 和 Ruby）中，可以在自身内部放置一个列表，这在使用列表来表示无限详细的分形时很有用。但是，我尝试在 Haskell 中执行此操作，但没有按预期工作：

--aList!!0!!0!!1 should be 1, since aList is recursively defined: the first element of aList is aList.
main = putStrLn $ show $ aList!!0!!0!!1

aList = [aList, 1]

程序没有打印1，而是产生了这个编译器错误：

[1 of 1] Compiling Main             ( prog.hs, prog.o )

prog.hs:3:12:
    Occurs check: cannot construct the infinite type: t0 = [t0]
    In the expression: aList
    In the expression: [aList, 1]
    In an equation for `aList': aList = [aList, 1]

是否可以像我在这里尝试做的那样在 Haskell 中放置一个列表？

4

5 回答 5

17
于 2013-09-11T00:09:43.693 回答
8

是的。如果您想要一个包含自身的值，则需要一个包含自身的类型。这没问题；例如，您可能喜欢玫瑰树，在 Data.Tree 中大致如下定义：

data Tree a = Node a [Tree a]

现在我们可以写：

recursiveTree = Node 1 [recursiveTree]
于 2013-09-10T23:37:09.497 回答
6

这对于 Haskell 中的列表类型是不可能的，因为每个元素必须是相同的类型，但是您可以创建一个数据类型来做到这一点。不过，我不确定您为什么要这样做。 

data Nested a
    = Value a
    | List [Nested a]
    deriving (Eq, Show)

nested :: Nested Int
nested = List [nested, Value 1]

(!) :: Nested a -> Int -> Nested a
(!) (Value _) _ = undefined
(!) (List xs) n = xs !! n

main = print $ nested ! 0 ! 0 ! 1

这将打印出来Value 1，并且这种结构可能会有一些用处，但我想它非常有限。

于 2013-09-10T23:38:51.347 回答
1

从“是的，你可以”到“不，你绝对不能”有几个答案。好吧，两者都是正确的，因为它们都解决了您问题的不同方面。

将“数组”添加到自身的另一种方法是允许任何内容的列表。

{-# LANGUAGE ExistentialQuantification #-}

data T = forall a. T a
arr :: [T]
arr = [T arr, T 1]

因此，这会将 arr 添加到自身，但您不能对它做任何其他事情，除非证明它是一个有效的构造并编译它。

由于 Haskell 是强类型的，访问列表元素会给你 T，你可以提取包含的值。但是该值的类型是什么？它是“forall a.a”——可以是任何类型，这实质上意味着根本没有函数可以用它做任何事情，甚至不能打印，因为这需要一个可以将任何类型 a 转换为 String 的函数。请注意，这不是 Haskell 特有的——即使在动态语言中也存在问题；没有办法弄清楚 的类型arr !! 1，你只能假设它是一个 Int。Haskell 与其他语言的不同之处在于它不允许您使用该函数，除非您可以解释表达式的类型。

这里的其他示例定义了归纳类型，这并不完全是您要问的，但它们显示了自引用的易处理处理。

以下是您如何实际制作一个明智的构造：

{-# LANGUAGE ExistentialQuantification #-}

data T = forall a. Show a => T a

instance Show T where -- this also makes Show [T],
        -- because Show a => Show [a] is defined in standard library
  show (T x) = show x

arr :: [T]
arr = [T arr, T 1]

main = print $ arr !! 1

现在由 T 包裹的内部值被限制为 Show 的任何实例（OOP 用语中的“Show 接口的实现”），因此您至少可以打印列表的内容。

请注意，之前我们不能仅将 arr 包含在其本身中，因为 a 和 [a] 之间没有任何共同点。但是，一旦您可以确定列表中的所有元素都支持的常见操作是什么，后一个示例就是一个有效的构造。如果您可以为 [T] 定义这样的函数，那么您可以将 arr 包含在其自身的列表中 - 此函数确定某些类型的 a 和 [a] 之间的共同点。

于 2013-09-11T10:01:41.283 回答
0

不，我们可以效仿：

data ValueRef a = Ref | Value a deriving Show

lref :: [ValueRef Int]
lref = [Value 2, Ref, Value 1]

getValue :: [ValueRef a] -> Int -> [ValueRef a]
getValue lref index = case lref !! index of
     Ref -> lref
     a -> [a]

并有结果：

>getValue lref 0
[Value 2]
>getValue lref 1
[Value 2,Ref,Value 1]

当然，我们可以重用Maybe a而不是ValueRef a

于 2013-09-11T15:19:01.083 回答