哈斯克尔比较了两个列表的长度，但其中一个是无限的？

Question

我想写一个函数，检查第一个列表是否比第二个列表长，其中一个列表是否可以是无限的。然而，我找不到一个有效的解决方案。

isLonger :: [a] -> [b] -> Bool
isLonger a b 
| listLength a > listLength b = True
|otherwise = False
listLength :: [a] -> Integer
listLength = foldr (flip $ const . (+1)) 0

Answer 1

@dfeuer的解决方案以聪明取胜，但就更典型的解决方案而言。。。

评论中提到的一种合理的方法是并行处理这两个列表；用完"；首先，这是较短的列表。一个简单的解决方案是在两个列表都不为空时递归：

isLonger :: [a] -> [b] -> Bool
isLonger (x:xs) (y:ys) = isLonger xs ys

并在其中一个列表变空时立即返回答案：

isLonger []     _  = False   -- list a <= list b
isLonger _      [] = True    -- list a > list b

如果两个列表同时用完(长度相等(，则第一个模式将匹配，从而在平局的情况下确定答案。

Answer 2

简单的旧自然数不会奏效，因为你无法在有限时间内计算无限列表的自然数长度。然而，懒惰自然数可以做到这一点。

import Data.Function (on)
data Nat = Z | S Nat
deriving (Eq, Ord)
len :: [a] -> Nat
len = foldr (const S) Z
isLonger :: [a] -> [b] -> Bool
isLonger = (>) `on` len

您可以更紧凑地使用列表来表示惰性自然数。

isLonger :: [a] -> [b] -> Bool
isLonger = (>) `on` (() <$)

当然，如果两个列表都是无限的，那么无论你做什么，你都注定会陷入无限循环

---

如果您担心定义不完整的列表以及无限的列表，那么您可以更轻松地使用Nat:的自定义Ord实例

instance Ord Nat where
compare Z Z = EQ
compare Z (S _) = LT
compare (S _) Z = GT
compare (S x) (S y) = compare x y
Z <= _ = True  -- lazy in the second argument
S _ <= Z = False
S x <= S y = x <= y
x >= y = y <= x
x > y = not (x <= y)
x < y = y > x

现在，如果第一个列表为空，即使第二个列表未定义，isLonger也将返回False。