Haskell-两个列表中的元组列表

Question

我试图实现一个函数(如下所述),它接受两个列表(每个或两个可能是无限的)并返回列表之间所有可能元素对的元组列表

zipInf :: [a] -> [b] -> [(a,b)]

(例如输出应该是这样的,但不一定非常像这样)

zipInf [0 .. 2] ['A' .. 'C'] ~> [(0,'A'),(1,'A'),(0,'B'),(1,'B'),(0,'C'),(2,'A'),(2,'B'),(1,'C'),(2,'C')]

zipInf [] [0 ..] ~> []

zipInf [0 ..] [] ~> []

take 9 (zipInf ['A'] [0 .. ]) ~> [('A',0),('A',1),('A',2),('A',3),('A',4),('A',5),('A',6),('A',7),('A',8)]

我开始像这样实现它:

zipInf :: [a] -> [b] -> [(a,b)]
zipInf [] _ = []
zipInf _ [] = []
zipInf

我想将列表提供给一个帮助函数来生成列表,但是我创建的列表无法编译,也不知道如何处理无限列表

辅助功能 -

oneList :: [a] -> [b] [(a,b)]
oneList [] _ = []
oneList x:xs y:ys = [(x,y)] ++ oneList

Answer 1

这是一个很棒的运动!

如果我们在无限表中布置您的输入对:

(0,A)  (1,A)  (2,A)  (3,A) ...
(0,B)  (1,B)  (2,B)  (3,B) ...
(0,C)  (1,C)  (2,C)  (3,C) ...
(0,D)  (1,D)  (2,D)  (3,D) ...
...

诀窍是以向上的斜条纹横穿桌子.用眼睛跟踪桌子.这张桌子的条纹是:

(0,A)
(0,B) (1,A)
(0,C) (1,B) (2,A)
(0,D) (1,C) (2,B) (3,A)
...

所有条纹都是有限的,但是表中的每个元素都在其中一个中,因此如果将它们连接在一起,则每个元素将出现在连接结果中的有限位置.

这是我建议的游戏规划:

实现stripes :: [[a]] -> [[a]]从上面的无限数组中提取条带列表(首先假设所有列表都是无限的,即不要担心这些[]情况;一旦你有了工作,就纠正它以处理可能有限的列表).

使用stripes,实现diagonal :: [[a]] -> [a]连接所有条纹(这是一个单行).

最后,通过应用diagonal特定的2D表来实现您的功能[[(a,b)]],这是我开始回答的表(并且可以使用嵌套列表理解以及其他各种方式构建).

笔记:

• zip名称具有误导性.这更像是笛卡尔积.

• 你知道你可以匹配模式中的模式,对吗？即如果f :: [[a]] -> something

  f ((x:xs):xss) = ...
  

  将您x作为第一行的第一个元素,是第一行xs的其余部分,并且xss是表的其余部分.

Answer 2

这是您发布的辅助函数：

oneList :: [a] -> [b] [(a,b)]
oneList [] _ = []
oneList x:xs y:ys = [(x,y)] ++ oneList

以下是它包含的语法错误：

• 您在类型注释中遗漏了一个箭头；它应该是

  oneList :: [a] -> [b] -> [(a,b)]
  

• 您需要将非平凡模式括在括号中，因此第二个方程应该开始

  oneList (x:xs) (y:ys) =
  

• oneList在返回列表之前接受两个参数，但在第二个方程的右侧，您尝试将其用作列表而不给它任何参数

（顺便说一句，如果您发布错误消息而不是仅仅说它无法编译，通常会对我们有所帮助。将我上面指出的错误与编译器给您的错误消息进行比较。）

但正如您所指出的，您的算法是错误的。

我觉得这是家庭作业，所以我只想给你一个提示。

zipInf应该

zipInf :: [a] -> [b] -> [(a,b)]
zipInf xs ys = thread (expand xs ys)

thread和expand是我要让你编写的两个带有类型签名的辅助函数

expand :: [a] -> [b] -> [[(a,b)]]
thread :: [[c]] -> [c]

expand相当简单。thread是你必须小心地以正确的顺序包含元素的地方（因此你不能只说thread zs = concat zs，即使类型是正确的）。

Answer 3

虽然这对于理解列表和Haskell一般来说是一个很好的练习,但它也是理解Applicative课程内容的一个很好的练习.特别是,[]实例Applicative.你zipInf想要的就是你liftA2 (,)

?: :t liftA2
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
?: :t (,)
(,) :: a -> b -> (a, b)
?: :t liftA2 (,)
liftA2 (,) :: Applicative f => f a -> f b -> f (a, b)

我们只需要确保它[]是一个Applicative.

?: :i []
...
instance Applicative [] -- Defined in `Control.Applicative'
...

所以这是一个Applicative.如果我们稍微注释一下我的类型,它可能会更容易理解

?: :t liftA2 (,) `asAppliedTo` []
[a] -> [b] -> [(a, b)]

是的,这是相同的类型.

?: liftA2 (,) [0..2] ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]

看起来很有效!所以你没有必要做任何事来写这个,并且它可以说比递归定义更容易理解.此外,您不必担心像滚动自己的解决方案时的边缘情况.

您也可以使用<$>(或fmap)和更具惯用性地编写它<*>.

?: (,) <$> [0..2] <*> ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]
?: take 9 $ (,) <$> "A" <*> [0..]
[('A',0),('A',1),('A',2),('A',3),('A',4),('A',5),('A',6),('A',7),('A',8)]

或者你可以充分利用Monad(在这种情况下这是非常不必要的):

?: do {n <- [0..2]; c <- ['A'..'C']; return (n, c)}
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C')]

此外,如果您想知道如何获得不同的语义,Applicative因为[]至少还有一个其他List实例Applicative:ZipList

?: :i ZipList
newtype ZipList a = ZipList {getZipList :: [a]}
    -- Defined in `Control.Applicative'
instance Functor ZipList -- Defined in `Control.Applicative'
instance Applicative ZipList -- Defined in `Control.Applicative'

此实例为其实例提供压缩样式语义Applicative.

?: getZipList $ (,) <$> ZipList [0..2] <*> ZipList ['A'..'C']
[(0,'A'),(1,'B'),(2,'C')]

这两个都是对Applicative类型类的很好的介绍,因为它们很容易获得,相当直观,有助于防止你制造错误,并且表明存在单个类型具有多个类型类实例的情况.

Answer 4

您需要oneList向xs和申请ys。

oneList :: [a] -> [b] -> [(a, b)]
oneList []     _      = []
oneList (x:xs) (y:ys) = (x, y) : oneList xs ys

由于 Haskell 很懒，无限列表会自动起作用。