8

我正在尝试实现一个函数（如下所述），它需要两个列表（每个或两个都可能是无限的）并返回列表之间所有可能元素对的元组列表

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
4

6 回答 6

11

这是一个很棒的练习！

如果我们将您的输入对布置在一个无限表中：

(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 table来实现您的功能[[(a,b)]]，这是我开始回答这个问题的表（并且可以使用嵌套列表理解以及其他各种方式构建）。

笔记：

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

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

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

    给你x作为第一行的第一个元素，是第一行xs的其余部分，并且xss是表格的其余部分。

于 2013-04-03T17:01:17.657 回答
5

这是您发布的辅助功能：

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在返回列表之前接受两个参数，但是在第二个等式的 rhs 中，您尝试将其用作列表而不给它任何参数

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

但正如您所注意到的，您的算法是错误的。

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

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，即使类型是正确的）。

于 2013-04-03T16:52:58.120 回答
5

虽然这是一个很好的练习，可以帮助您理解列表和一般的 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')]

看起来它有效！所以你不需要做任何事情来写这个，它可以说比递归定义更容易理解。此外，您不必像推出自己的解决方案时那样担心边缘情况。

您也可以使用<$>(or 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')]

此外，如果您想知道如何从Applicativefor[]中获得不同的语义，至少还有一个其他 List 实例 for 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，因为它们很容易获得，相当直观，有助于防止你犯错误，并表明在某些情况下单个类型具有多个类型类的实例。

于 2014-04-07T06:05:19.873 回答
1

您需要oneList申请xs和ys。

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

由于 Haskell 是惰性的，无限列表将自动工作。

于 2013-04-03T16:52:47.400 回答
1

重要提示：请参阅下面 Will Ness 的评论。

您的问题意味着顺序无关紧要。（但由于列表可能是无限的，因此顺序可能比您想象的更重要！）无论如何，如果顺序无关紧要，并且您遇到了列表推导，那是您可以使用的一种方法。这是一个例子。

λ> let xs = "abcdef"
λ> let ys = "ABCDEFGHI"
λ> [(x,y) | x <- xs, y <- ys]
[('a','A'),('a','B'),('a','C'),('a','D'),('a','E'),('a','F'),('a','G'),('a','H'),('a','I'),('b','A'),('b','B'),('b','C'),('b','D'),('b','E'),('b','F'),('b','G'),('b','H'),('b','I'),('c','A'),('c','B'),('c','C'),('c','D'),('c','E'),('c','F'),('c','G'),('c','H'),('c','I'),('d','A'),('d','B'),('d','C'),('d','D'),('d','E'),('d','F'),('d','G'),('d','H'),('d','I'),('e','A'),('e','B'),('e','C'),('e','D'),('e','E'),('e','F'),('e','G'),('e','H'),('e','I'),('f','A'),('f','B'),('f','C'),('f','D'),('f','E'),('f','F'),('f','G'),('f','H'),('f','I')]

请注意，'a'首先打印所有涉及的元组，然后是涉及的元组'b'，依此类推。为什么这很重要？好吧，假设列表是无限的。像这样的查询将立即返回：

(1,'a') `elem` [(x,y) | x <- [1..], y <- ['a'..]]

但是像这样需要很长时间：

(200000,'a') `elem` [(x,y) | x <- [1..], y <- ['a'..]]

如果顺序很重要，或者您还没有遇到列表推导，或者不想使用它们，那么 luqui 的方法可能就是您正在寻找的。

于 2013-04-04T10:47:16.850 回答
0

您可以通过使用列表推导非常简单地做到这一点。

zip :: [a] -> [b] -> [(a,b)]
zip [] _ = [] 
zip _ [] = []
zip as bs = [(a, b) | a <- as, b <- bs]

它适用于有限列表和无限列表。当然，您希望其中至少有一个是有限的，或者它只是head as和的所有组合bs。

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

> take 50 $ zip [0..] ['A'..'C']
[(0,'A'),(0,'B'),(0,'C'),(1,'A'),(1,'B'),(1,'C'),(2,'A'),(2,'B'),(2,'C'),(3,'A'),(3,'B'),(3,'C'),(4,'A'),(4,'B'),(4,'C'),(5,'A'),(5,'B'),(5,'C'),(6,'A'),(6,'B'),(6,'C'),(7,'A'),(7,'B'),(7,'C'),(8,'A'),(8,'B'),(8,'C'),(9,'A'),(9,'B'),(9,'C'),(10,'A'),(10,'B'),(10,'C'),(11,'A'),(11,'B'),(11,'C'),(12,'A'),(12,'B'),(12,'C'),(13,'A'),(13,'B'),(13,'C'),(14,'A'),(14,'B'),(14,'C'),(15,'A'),(15,'B'),(15,'C'),(16,'A'),(16,'B')]

> take 50 $ zip [0..] [1..]
[(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(0,10),(0,11),(0,12),(0,13),(0,14),(0,15),(0,16),(0,17),(0,18),(0,19),(0,20),(0,21),(0,22),(0,23),(0,24),(0,25),(0,26),(0,27),(0,28),(0,29),(0,30),(0,31),(0,32),(0,33),(0,34),(0,35),(0,36),(0,37),(0,38),(0,39),(0,40),(0,41),(0,42),(0,43),(0,44),(0,45),(0,46),(0,47),(0,48),(0,49),(0,50)]
于 2020-07-31T12:28:38.230 回答