Haskell比较了两个列表的长度，但其中一个是无限的？

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

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

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` (() <$)

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

Answer 2

@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

如果两个列表同时运行（长度相等），第一个模式将匹配，以便在平局的情况下确定答案。