Haskell 比较两个列表的长度但其中一个是无限的?
Haskell comparing two lists' lengths but one of them is infinite?
我想写一个函数来检查第一个列表是否比第二个列表长,并且其中一个可以是无限的。但是我找不到有效的解决方案。
isLonger :: [a] -> [b] -> Bool
isLonger a b
| listLength a > listLength b = True
|otherwise = False
listLength :: [a] -> Integer
listLength = foldr (flip $ const . (+1)) 0
普通的旧自然数无法解决问题,因为您无法在有限时间内计算无限列表的自然数长度。不过lazy自然数可以做到
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` (() <$)
当然,如果两个列表都是无限的,那么无论你做什么都注定会陷入无限循环。
如果您担心不完全定义的列表以及无限的列表,您可以使用自定义 Ord
实例来更懒一点 Nat
:
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
将 return False
即使第二个列表未定义。
@dfeuer 的解决方案以聪明取胜,但就更典型的解决方案而言...
评论中提到的一种合理方法是并行处理两个列表,然后找出哪个“运行先出局”——这是较短的列表。一个简单的解决方案是在两个列表都是 non-empty:
时递归
isLonger :: [a] -> [b] -> Bool
isLonger (x:xs) (y:ys) = isLonger xs ys
和 return 一旦其中一个列表变空就会得到答案:
isLonger [] _ = False -- list a <= list b
isLonger _ [] = True -- list a > list b
如果两个列表 运行 同时出现(长度相等),第一个模式将匹配,因此在平局的情况下将确定答案。
我想写一个函数来检查第一个列表是否比第二个列表长,并且其中一个可以是无限的。但是我找不到有效的解决方案。
isLonger :: [a] -> [b] -> Bool
isLonger a b
| listLength a > listLength b = True
|otherwise = False
listLength :: [a] -> Integer
listLength = foldr (flip $ const . (+1)) 0
普通的旧自然数无法解决问题,因为您无法在有限时间内计算无限列表的自然数长度。不过lazy自然数可以做到
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` (() <$)
当然,如果两个列表都是无限的,那么无论你做什么都注定会陷入无限循环。
如果您担心不完全定义的列表以及无限的列表,您可以使用自定义 Ord
实例来更懒一点 Nat
:
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
将 return False
即使第二个列表未定义。
@dfeuer 的解决方案以聪明取胜,但就更典型的解决方案而言...
评论中提到的一种合理方法是并行处理两个列表,然后找出哪个“运行先出局”——这是较短的列表。一个简单的解决方案是在两个列表都是 non-empty:
时递归isLonger :: [a] -> [b] -> Bool
isLonger (x:xs) (y:ys) = isLonger xs ys
和 return 一旦其中一个列表变空就会得到答案:
isLonger [] _ = False -- list a <= list b
isLonger _ [] = True -- list a > list b
如果两个列表 运行 同时出现(长度相等),第一个模式将匹配,因此在平局的情况下将确定答案。