C. *_*ann 29
应用于length未知列表通常是一个坏主意,实际上是由于无限列表,并且在概念上是因为通常事实证明你实际上并不关心长度.
你在评论中说:
我对Haskell很新,所以现在,不是无限结构使我的程序非常脆弱吗？
并不是的.虽然我们中的一些人希望有更好的方法来区分必然有限和必然无限的数据,但是当您逐步创建,处理和检查惰性结构时,您总是安全的.计算长度显然不是渐进的,但检查是否长度为高于或低于一定的临界值是,很多时候这就是你想做的事!
一个简单的案例是测试非空列表.isNonEmpty xs == length xs > 0是一个糟糕的实现,因为它检查无限数量的元素,当检查一个元素就足够了!比较一下:
isNonEmpty [] = False
isNonEmpty (_:_) = True
这不仅是安全的,适用于一个无限列表,它也更有限名单更有效-它在列表的长度只需要一定的时间,而不是时间的线性.它也是标准库函数null的实现方式.
为了对相对于截止值进行长度测试进行推广,您显然需要检查列表的大小与您要比较的长度.我们可以使用标准库函数完成此操作,而不是更多drop:
longerThan :: Int -> [a] -> Bool
longerThan n xs = isNonEmpty $ drop n xs
给定一个长度n和一个(可能是无限的)列表xs,这会删除它们存在的第一个n元素xs,然后检查结果是否为非空.因为drop如果生产的空单n比列表的长度较大,这正常工作对所有正n(唉,有没有非负整数类型,例如自然数,在标准库).
这里的关键点是,在大多数情况下,将列表视为迭代流而不是简单的数据结构会更好.如果可能,您希望执行转换,累积,截断等操作,并生成另一个列表作为输出或仅检查已知有限量的列表,而不是尝试一次处理整个列表.
如果你使用这种方法,你的函数不仅可以在有限列表和无限列表上正常工作,而且它们还可以从懒惰和GHC优化器中获益更多,并且可能运行得更快并且使用更少的内存.
小智 26
该停机问题首先证明了假设停机甲骨文存在,然后写一个函数,做了什么,甲骨文说会发生相反的不可解.我们在这里重现:
isInfinite :: [a] -> Bool
isInfinite ls = {- Magic! -}
现在,我们想要制作一个impossibleList与isInfinite它应该做的相反的列表.所以,如果impossibleList是无限的,它实际上是[],如果它不是无限的,它就是something : impossibleList.
-- using a string here so you can watch it explode in ghci
impossibleList :: [String]
impossibleList =
case isInfinite impossibleList of
True -> []
False -> "loop!" : impossibleList
自己尝试用ghci isInfinite = const True和isInfinite = const False.
scl*_*clv 12
isInfinite x = length x `seq` False
小智 12
我们不需要解决停机问题来安全地调用'长度'.我们只需要保守; 接受所有具有有限性证据的东西,拒绝所有没有证据的东西(包括许多有限列表).这正是类型系统的用途,因此我们使用以下类型(t是我们忽略的元素类型):
terminatingLength :: (Finite a) => a t -> Int
terminatingLength = length . toList
有限类只包含有限列表,因此类型检查器将确保我们有一个有限的参数.有限的成员资格将是我们有限的证明."toList"函数只是将有限值转换为常规Haskell列表:
class Finite a where
toList :: a t -> [t]
现在我们的实例是什么？我们知道空列表是有限的,所以我们创建一个数据类型来表示它们:
-- Type-level version of "[]"
data Nil a = Nil
instance Finite Nil where
toList Nil = []
如果我们'将'一个元素放在有限列表上,我们得到一个有限列表(例如,如果"xs"是有限的,则"x:xs"是有限的):
-- Type-level version of ":"
data Cons v a = Cons a (v a)
-- A finite tail implies a finite Cons
instance (Finite a) => Finite (Cons a) where
toList (Cons h t) = h : toList t -- Simple tail recursion
任何调用我们的terminatingLength函数的人现在必须证明他们的列表是有限的,否则他们的代码将无法编译.这并没有消除停机问题,但我们已将其转移到编译时而不是运行时.编译器可能在尝试确定有限元的成员资格时挂起,但这比生成程序在给出一些意外数据时挂起要好.
需要注意的是:Haskell的'ad-hoc'多态性允许在代码中的其他点声明几乎任意的有限实例,而终止长度将接受这些作为有限证明,即使它们不是.这不是太糟糕了; 如果有人试图绕过你的代码的安全机制,他们会得到他们应得的错误;)
不 - 你最好估计一下.请参阅暂停问题.