在haskell中实现解压缩功能

Question

我正在尝试实现解压缩功能,我做了以下代码但是我收到了错误.

myUnzip [] =()
myUnzip ((a,b):xs) = a:fst (myUnzip xs)  b:snd (myUnzip xs)

我知道问题出在第二行的右侧,但我确实知道如何改进它.任何提示请.

我得到的错误是

ex1.hs:190:22:
Couldn't match expected type `()' with actual type `[a0]'
In the expression: a : fst (myUnzip xs) b : snd (myUnzip xs)
In an equation for `myUnzip':
    myUnzip ((a, b) : xs) = a : fst (myUnzip xs) b : snd (myUnzip xs)


ex1.hs:190:29:
Couldn't match expected type `(t0 -> a0, b0)' with actual type `()'
In the return type of a call of `myUnzip'
In the first argument of `fst', namely `(myUnzip xs)'
In the first argument of `(:)', namely `fst (myUnzip xs) b'

ex1.hs:190:49:
Couldn't match expected type `(a1, [a0])' with actual type `()'
In the return type of a call of `myUnzip'
In the first argument of `snd', namely `(myUnzip xs)'
In the second argument of `(:)', namely `snd (myUnzip xs)'

Answer 1

你可以通过两次遍历列表来低效地完成它

myUnzip [] = ([], []) -- Defaults to a pair of empty lists, not null
myUnzip xs = (map fst xs, map snd xs)

但这并不是很理想,因为与仅循环一次相比,它必然会非常慢.为了解决这个问题,我们必须以递归方式进行

myUnzip [] = ([], [])
myUnzip ((a, b):xs) = (a : ???, b : ???)
    where ??? = myUnzip xs

我会让你填补空白,但是从这里开始应该是直截了当的,只要查看类型签名myUnzip并找出你可以代替问号的地方.where ??? = myUnzip xs

Answer 2

我认为展示两种替代解决方案可能会很有趣。在实践中你不会使用这些，但它们可能会让你对 Haskell 的一些可能性敞开心扉。

首先，有一个使用折叠的直接解决方案 -

unzip' xs = foldr f x xs
  where
    f (a,b) (as,bs) = (a:as, b:bs)
    x               = ([],   [])

这使用一个被调用的组合器foldr来遍历列表。相反，您只需定义组合函数f，该函数告诉您如何将(a,b)一对列表与一对列表组合(as, bs)，并定义初始值x。

其次，记住有一个好看的解决方案

unzip'' xs = (map fst xs, map snd xs)

看起来很整洁，但执行输入列表的两次迭代。能够写出像这样简单的东西会很好，但它只遍历输入列表一次。

我们几乎可以使用Foldl库来实现这一点。有关为什么它不太有效的解释，请参阅最后的注释 - 也许有更多知识/时间的人可以解释修复。

首先，导入库并定义身份折叠。您可能必须先运行cabal install foldl才能安装库。

import Control.Applicative
import Control.Foldl

ident = Fold (\as a -> a:as) [] reverse

然后，您可以定义折叠以提取对列表的第一个和第二个组件，

fsts = map fst <$> ident
snds = map snd <$> ident

最后你可以将这两个折叠组合成一个解压缩列表的折叠

unzip' = (,) <$> fsts <*> snds

这并不完全有效的原因是，尽管您只遍历列表一次以提取对，但它们将以相反的顺序提取。这就是需要reverse在 的定义中额外调用的原因ident，这会导致对列表的额外遍历，以将其放置在正确的顺序中。我很想知道一种方法来解决这个问题（我希望当前的Foldl库不可能，但可能有一个类似的Foldr库，它放弃流式传输以保留输入的顺序）。

请注意，这些都不适用于无限列表。使用的解决方案Foldl永远无法处理无限列表，因为在列表终止之前您无法观察左折叠的值。

但是，使用正确折叠的版本应该可以工作 - 但目前它还不够懒惰。在定义中

unzip' xs = foldr f x xs
  where
    f (a,b) (as,bs) = (a:as, b:bs) -- problem is in this line!
    x               = ([],   [])

模式匹配要求我们打开第二个参数中的元组，这需要评估折叠的一个步骤，这需要打开另一个元组，这需要评估折叠的一个步骤，等等。但是，如果我们使用无可辩驳的模式匹配（总是成功，无需检查模式）我们得到了恰到好处的懒惰 -

unzip'' xs = foldr f x xs
  where
    f (a,b) ~(as,bs) = (a:as, b:bs)
    x                = ([],   [])

所以我们现在可以做

>> let xs = repeat (1,2)
>> take 10 . fst . unzip'  $ xs
^CInterrupted
<< take 10 . fst . unzip'' $ xs
[1,1,1,1,1,1,1,1,1,1]