haskell - Data.List.Ordered.unionAll 通过比较无限列表

Question

所以我有 2 个排序列表作为输入，可以是无限的。
我必须编写一个函数 prod，它基本上按排序顺序返回笛卡尔积坐标的乘积。

例子:

prod [2,4,5,10] [2,3] -> [4,6,8,10,12,15,20,30]

对于有限列表，它很简单

import Data.List
prod xs ys = sort [x*y | x<-xs, y<-ys]

但问题是当我尝试将它与无限列表一起使用时。我在想，因为输入已排序，我可以使用 Data.List.Ordered.unionAllBy ，但我无法理解如何使用它。比较选项让我感到困惑。

所以我可以使用我写的函数:

sequence2 xs ys = [[i*j| i<-xs]|j<-ys]

例子:

sequence2 [2,4,5] [3,4,5] -> [[6,12,15],[8,16,20],[10,20,25]]

我想我的解决方案看起来像:

Data.List.Ordered.unionAllBy (comparison) (sequence' xs ys)

任何提示我如何修改它以使用无限列表？

Answer 1

比较传递给 unionAllBy是与 compare 类型相同并遵循相同规则的函数来自 Ord 的函数实例。如果您有 Ord您可以使用的实例 unionAll 而不是 unionAllBy .

unionAllBy ::          (a -> a -> Ordering) -> [[a]] -> [a]
unionAll   :: Ord a =>                         [[a]] -> [a]
compare    :: Ord a =>  a -> a -> Ordering

unionAll = unionAllBy compare

比较函数接受两个对象并说明它们的顺序: LT , EQ , 或 GT .最好的解释是什么 compare应该做的可能是它在 Ord class in the standard prelude 中的默认定义

compare x y  
     | x == y    =  EQ  
     | x <= y    =  LT  
     | otherwise =  GT  

x <= y           =  compare x y /= GT  
x <  y           =  compare x y == LT  
x >= y           =  compare x y /= LT  
x >  y           =  compare x y == GT

unionAll函数将联合您的 sequence2列表，以便从列表之间删除重复项。 unionAll不会删除单个输入列表中存在的重复项。

> unionAll $ sequence2 [2,4,5] [3,4,5]
[6,8,10,12,15,16,20,25]
                 ^
                 only one twenty

它也会变平 sequence2按顺序应用于无限列表

> take 12 . unionAll $ sequence2 [2,4..] [3,5..]
[6,10,12,14,18,20,22,24,26,28,30,34]

如果要保留重复项，请使用 mergeAll 反而。

> mergeAll $ sequence2 [2,4,5] [3,4,5]
[6,8,10,12,15,16,20,20,25]
                 ^  ^
                 two twenties