Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Haskell函数式编程入门里的一个小问题 #145

Open
vincenteof opened this issue Jan 21, 2019 · 3 comments
Open

Haskell函数式编程入门里的一个小问题 #145

vincenteof opened this issue Jan 21, 2019 · 3 comments

Comments

@vincenteof
Copy link

@vincenteof vincenteof commented Jan 21, 2019

书里的练习7.2.4是要求一种遍历[(x, y) | x <- [1 ..], y <- [1 ..]]里所有元组的方法。这个问题跟证明有理数集可数是一样的,我知道如何按照那种方式去生成。

书里的提示貌似跟那种方式不太一样,是这样的:

定义一个类似于 concat 的函数 interLeave,这个函数可以将两个无穷的列表合在一起。使用 interLeave 函数与 foldr 函数定义一个函数 interLeaveLists,它与 concat 功能相似。再使用 interLeaveLists 对 [[(x,y)| y <- [1..]] | x <- [1..]]进行连接

我尝试了一下,大概是这样的:

interLeave :: [a] -> [a] -> [a]
interLeave xs ys = foldr (\(x, y) acc -> x : y : acc) [] (zip xs ys)

interLeaveLists :: [[a]] -> [a]
interLeaveLists = foldr1 interLeave

allResults = interLeaveLists [[(x, y) | y <- [1..]] | x <- [1..]]

结果是无穷递归了,不知道如何按照书里的思路去fix这个问题呢,求教。

@kalxd
Copy link

@kalxd kalxd commented Feb 14, 2019

没看过这本书,如代码上来看,foldr一条无穷长的列表自然是无穷递归了。可以试着take一部分出来。

interLeave :: [a] -> [a] -> [a]
interLeave xs ys = foldr (\(x, y) acc -> x : y : acc) [] $ take 10 $ zip xs ys

@SnowOnion
Copy link

@SnowOnion SnowOnion commented Mar 23, 2019

我看了下《Haskell函数式编程入门(第2版)第1卷》的练习 7.2.4。
按照书里提示的思路,得到的不是证有理数集可数的那种康托对角线顺序,但是仍然能遍历到每一个元素。
我经过几次尝试得到的可行解是:

interleave :: [a] -> [a] -> [a]
interleave (x:xs) ys = x : interleave' xs ys
interleave' xs (y:ys) = y : interleave xs ys

interleaveLists :: [[a]] -> [a]
interleaveLists = foldr interleave (repeat undefined)

results = interleaveLists [[(x, y) | y <- [1..]] | x <- [1..]]

效果:

> take 10 results 
[(1,1),(2,1),(1,2),(3,1),(1,3),(2,2),(1,4),(4,1),(1,5),(2,3)]
> import Data.List(findIndex)
> findIndex (==(5,5)) results 
Just 143
> findIndex (==(10,10)) results 
Just 9727

解说:

  1. 为啥选择叫 interleave 而不叫书上的 interLeave……因为 interleave 整体是一个单词……
  2. (repeat undefined) 起“占位符”作用,在 foldr + 无穷列表 的组合下,它永远不会被求值到。如果用 foldr1,反倒是会导致 foldr1 interleaveLists xs 里面 xs 的第一个元素没法被用到。
  3. 如上所示,实现 interleave 不需要 foldr。另外,我第一次尝试时写的是 interleave (x:xs) (y:ys) = x : y : interleave xs ys,这也会导致求值 take 10 results 不终止;我知道原因了,你呢?( ゚∀。)
  4. 心得:“只处理无穷长的输入”可以比“只处理有穷长的输入”写得更简单……

@vincenteof
Copy link
Author

@vincenteof vincenteof commented Mar 26, 2019

@SnowOnion interleave (x:xs) (y:ys) = x : y : interleave xs ys 貌似和 interLeave xs ys = foldr (\(x, y) acc -> x : y : acc) [] (zip xs ys) 会有类似的问题,在后续 foldr 的调用中会导致foldr结果里惰性的部分被求值,然后引起了另一个 interleave 的过程,导致无限递归。你给出的可行解里 interleaveinterleave' 互相调用避免了这个问题,interesting,学习到了。
p.s. 这种方法结果的遍历顺序感觉也蛮有意思的,以1开头的序对迭代得是最快的,越往后越来越慢。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants