在Haskell中相互依赖的无限列表?

huangapple go评论55阅读模式
英文:

Infinite lists that depend on each other in Haskell?

问题

我正在处理一个编程练习,目标是编写一个函数,以获取Hofstadter的"Figure-Figure"序列的第N个索引处的项。

与使用公式提出一个基本解决方案不同,我认为生成一个无限列表来表示该序列然后进行索引会是一个有趣的挑战。

这是我的初始方法,但是在尝试计算超过前两个项时会挂起。

hof :: Int -> Int
hof = (!!) seqA
  where
    seqA = 1 : zipWith (+) seqA seqB
    seqB = 2 : filter (`notElem` seqA) [3..]

seqA表示项的序列,而seqB是它们之间的差异。

尽管我不太了解如何使用seq,但我尝试使用它来严格评估所需项之前的项,如下所示。

hof :: Int -> Int
hof 0 = 1
hof n = seq (hof $ n - 1) $ seqA !! n
  where
    seqA = 1 : zipWith (+) seqA seqB
    seqB = 2 : filter (`notElem` seqA) [3..]

尝试计算超过第一个索引的值时,这也会挂起。

在ghci中尝试了一下后,我找到了一种奇怪的方法来使它正常工作

ghci> seqB = [2, 4, 5, 6]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> seqB = 2 : filter (`notElem` seqA) [3..]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> hof = (!!) seqA

通过给seqB一个初始值,并在之后重新定义seqAseqB,它似乎可以正常工作。不过我注意到,将较大的值传递给hof似乎会根据我最初放入seqB列表中的项数量而产生不同的结果。当我在ghci中重新定义函数时,它是否仍然使用以前对它进行调用的函数的旧版本?

我想知道为什么这在ghci中有效,以及是否有可能使用类似的技术编写这段代码的工作版本。提前感谢您的回答!

英文:

I am working on a programming exercise where the goal is to write a function to get the term at the Nth index of Hofstadter's Figure-Figure sequence.

Rather come up with a basic solution using the formula, I thought it would be an interesting challenge to generate an infinite list to represent the sequence and then index it.

This was my initial approach, however, it hangs when trying to calculate anything past the first two terms.

hof :: Int -> Int
hof = (!!) seqA
  where
    seqA = 1 : zipWith (+) seqA seqB
    seqB = 2 : filter (`notElem` seqA) [3..]

seqA represents the sequence of terms, and seqB is the differences between them.

Though I don't really understand how to use seq, I tried using it to strictly evaluate the terms that come before the desired one, like shown below.

hof :: Int -> Int
hof 0 = 1
hof n = seq (hof $ n - 1) $ seqA !! n
  where
    seqA = 1 : zipWith (+) seqA seqB
    seqB = 2 : filter (`notElem` seqA) [3..]

This also hangs when trying to calculate values past the first index.

After playing around in ghci, I found a way to get this to work in a weird way

ghci> seqB = [2, 4, 5, 6]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> seqB = 2 : filter (`notElem` seqA) [3..]
ghci> seqA = 1 : zipWith (+) seqA seqB
ghci> hof = (!!) seqA

By giving seqB and initial value and redefining both seqA and seqB afterwards, it seems to function normally. I did notice, however, that the result of passing larger values to hof seems to give different results based on how many terms I initially put in the seqB list. When I redefine the function in ghci, does it still use the older version for functions that call it previous to its redefinition?

I would like to know why this works in ghci and whether it's possible to write a working version of this code using a similar technique. Thanks in advance!

答案1

得分: 1

问题在于seqA是无限的,因此(notElem seqA) x永远不会返回True。如果它发现xseqA的第一个元素,那很好:它可以返回False。但如果它没有看到x,它希望继续寻找:也许x是下一个元素!列表永不结束,所以它无法得出结论x肯定不存在。

这是初学者经常犯的经典错误,尝试过滤一个无限的列表,并期望列表在某个点结束。通常,答案是使用类似于

x notElem (takeWhile (< x) infList)

的方法。这样,一旦找到一个大于x的数字,你的程序就放弃了寻找x。当然,这只适用于排序的列表。根据你的方程式,它看起来可能会产生升序的列表,如果是这种情况,它会起作用,但我还没有经过代数计算。如果你的列表不是按升序排列的,你将需要设计一些其他停止条件,以避免无限递归。

英文:

The problem is that seqA is infinite, and so

(`notElem` seqA) x

can never return True. If it sees that x is the first element of seqA, then great: it can return False. But if it doesn't see x, it wants to keep looking: maybe x is the next element! The list never ends, so there's no way it can conclude x is definitely not present.

This is a classic mistake beginners make, trying to filter an infinite list and expecting the list to end at some point. Often, the answer is to use something like

x `notElem` (takeWhile (&lt;= x) infList)

instead. This way, your program gives up on searching for x once it's found a number above x. This only works if your lists are sorted, of course. Your equations look like they probably produce ascending lists, in which case it would work, but I haven't worked through the algebra. If your lists aren't in ascending order, you'll need to design some other stopping condition to avoid the infinite recursion.

答案2

得分: 1

下面是代码部分的翻译:

complement = go 1 where
    go i xs@(x:xt) = case compare i x of
        LT -> i : go (i+1) xs
        EQ -> i+1 : go (i+2) xt
        GT -> go i xt -- this case should be impossible
    go i [] = [i..] -- this case is irrelevant for our purposes
seqA = 1 : zipWith (+) seqA seqB
seqB = complement seqA
complement = go i where
    go i xs@(x:xt) = case compare i x of
        LT -> i : go (i+1) xs
        EQ -> go (i+1) xt
        GT -> go i xt -- still impossible
    go i [] = [i..] -- still irrelevant
seqA = 1 : zipWith (+) seqA seqB
seqB = 2 : 4 : drop 2 (complement seqA)

希望这些翻译对您有所帮助。

英文:

The other answer tells you the problem with your approach, and suggests a great fix. I thought it might be fun to try to work out a slightly more efficient solution, though; it seems a shame to keep checking the beginning of seqA over and over during our membership calls. Here's the idea I had: the point is for seqB to be the complement of seqA, right? Well, what if we just directly define a complement function? Like this:

complement :: Integer -&gt; [Integer] -&gt; [Integer]
complement = go 1 where
	go i xs@(x:xt) = case compare i x of
		LT -&gt; i : go (i+1) xs
		EQ -&gt; i+1 : go (i+2) xt
		GT -&gt; go i xt -- this case should be impossible
	go i [] = [i..] -- this case is irrelevant for our purposes

The EQ case is a bit suspect; it doesn't work for general increasing input sequences. (But see below.) Anyway, with this definition in place, the two sequences can be quite naturally defined:

seqA, seqB :: [Integer]
seqA = 1 : zipWith (+) seqA seqB
seqB = complement seqA

Try it in ghci:

&gt; take 10 seqA
[1,3,7,12,18,26,35,45,56,69]

Nice. Now, if we fix up the EQ case to work properly for all (increasing) input sequences, it would have to look like this:

complement :: Integer -&gt; [Integer] -&gt; [Integer]
complement = go i where
	go i xs@(x:xt) = case compare i x of
		LT -&gt; i : go (i+1) xs
		EQ -&gt; go (i+1) xt
		GT -&gt; go i xt -- still impossible
	go i [] = [i..] -- still irrelevant

Unfortunately, our definitions of seqA and seqB above don't quite work any more. The right first value for seqB depends on whether 2 is in seqA, but whether 2 is in seqA depends on whether the first value of seqB is 1 or not... Luckily, because seqA grows much faster than seqB, we only have to prime the pump a little.

seqA, seqB :: [Integer]
seqA = 1 : 3 : 7 : zipWith (+) (drop 2 seqA) (drop 2 seqB)
seqB = complement seqA
-- OR
seqA = 1 : zipWith (+) seqA seqB
seqB = 2 : 4 : drop 2 (complement seqA)

Try it in ghci:

&gt; take 10 seqA
[1,3,7,12,18,26,35,45,56,69]

The definition of seqX is a bit less natural, but the definition of complement is a bit more natural, so there seems to be something of a tradeoff there.

答案3

得分: 0

对于此部分的回答:

> 当我在ghci中重新定义函数时,对于之前使用它的函数,它是否仍然使用旧版本?

是的,它必须按照这种方式工作。在ghci提示符下的绑定不是像在命令式语言中那样可变的变量,它们应该与Haskell的其他部分中的变量工作方式相同。

所以当你有这样的情况:

ghci&gt; a = 1
ghci&gt; b = [a]
ghci&gt; b
[1]

a只是1的名称,b只是[1]的名称。后者是通过查看a是一个名称的值来计算的,但它绝对是[1],而不是表达式[a]b引用的。

ghci&gt; a = 2
ghci&gt; b
[1]

执行a = 2不会改变a引用的,它只会改变ghci提示符中可用的环境状态。这不会影响a是名称为1时计算的任何值;它们是纯粹的值,且保持不变。

一个简单的思考方式是,a = 2不是“改变a”,它只是引入了一个新的、独立的绑定。因为它恰好与现有绑定同名,新绑定遮蔽了旧绑定,使你无法在以后的表达式中引用旧绑定。但旧绑定没有发生任何变化。

实际上,在编译模块中,在可以为一个名称有多个绑定的上下文中,你将看到完全相同的行为(如果你使用let遮蔽函数参数,或嵌套let等)。除了一个绑定之外,所有其他绑定都将无法访问,但在阴影绑定的定义中使用的内容保持完全不变;它们不会重新评估,就好像它们是在新绑定中定义的一样。

因此,考虑到这一点,很容易解释为什么这样工作:

ghci&gt; seqB = [2, 4, 5, 6]
ghci&gt; seqA = 1 : zipWith (+) seqA seqB
ghci&gt; seqB = 2 : filter (`notElem` seqA) [3..]
ghci&gt; seqA = 1 : zipWith (+) seqA seqB
ghci&gt; hof = (!!) seqA

这与如果你这样定义它是大致相同的:

ghci&gt; seqB_old = [2, 4, 5, 6]
ghci&gt; seqA_old = 1 : zipWith (+) seqA_old seqB_old
ghci&gt; seqB_new = 2 : filter (`notElem` seqA_old) [3..]
ghci&gt; seqA_new = 1 : zipWith (+) seqA_new seqB_new
ghci&gt; hof = (!!) seqA_new
  1. seqB_old只是一个有限列表。
  2. 因为zipWith在最短列表的长度处停止,seqA_old也只是一个有限列表,尽管它是根据自身定义的。
  3. seqB_new是一个无限列表,只需要过滤每个元素与有限列表seqA_old的任何元素。这不会陷入amalloy指出的问题,但实际上并不是你试图定义的正确列表。
  4. seqA_new是根据自身定义的,但seqB_new是根据seqA_old定义的,而不是这个新版本。根本没有互相递归的发生。
英文:

As an answer to this part:

> When I redefine the function in ghci, does it still use the older version for functions that call it previous to its redefinition?

Yes, that's the way it has to work. Bindings at the ghci prompt are not mutable variables as you would have in an imperative language, they're supposed to work the same way as variables do in every other part of Haskell.

So when you have this:

ghci&gt; a = 1
ghci&gt; b = [a]
ghci&gt; b
[1]

a is just a name for 1, and b is just a name for [1]. The latter was calculated by from the expression [a] by seeing what value a was a name for, but it is absolutely the value [1] and not the expression [a] that b refers to.

ghci&gt; a = 2
ghci&gt; b
[1]

Executing a = 2 doesn't change the value referred to by a, it just changes the state of the environment available at the ghci prompt. This cannot affect any values that were calculated when a was a name for 1; they were and remain pure values.

An easy way to think about it is that a = 2 is not "changing a", it's just introducing a new and separate binding. Because it happens to have the same name as an existing one the new one shadows the old one, making the old one impossible for you to refer to in any future expressions. But nothing about the old one has been changed.

And you will in fact see exactly the same behaviour in a compiled module in contexts where you can have multiple bindings for one name (if you shadow a function argument with a let, or nest lets, etc). All but one of them will be inaccessible, but things that were defined in terms of the shadowed binding remain exactly the same; they aren't re-evaluated as if they were defined in terms of the new binding.

So with that in mind, it becomes easy to explain why this works:

ghci&gt; seqB = [2, 4, 5, 6]
ghci&gt; seqA = 1 : zipWith (+) seqA seqB
ghci&gt; seqB = 2 : filter (`notElem` seqA) [3..]
ghci&gt; seqA = 1 : zipWith (+) seqA seqB
ghci&gt; hof = (!!) seqA

It's much the same as if you had defined it this way:

ghci&gt; seqB_old = [2, 4, 5, 6]
ghci&gt; seqA_old = 1 : zipWith (+) seqA_old seqB_old
ghci&gt; seqB_new = 2 : filter (`notElem` seqA_old) [3..]
ghci&gt; seqA_new = 1 : zipWith (+) seqA_new seqB_new
ghci&gt; hof = (!!) seqA_new
  1. seqB_old is just a finte list
  2. Because zipWith stops at the length of the shortest list, seqA_old is also just a finite list, even though it's defined in terms of itself.
  3. seqB_new is an infinite list that just has to filter each element against any of the elements of the finite list seqA_old; this doesn't get caught up in the problem amalloy points out, but it isn't actually the correct list you were trying to define
  4. seqA_new is defined in terms of itself, but seqB_new was defined in terms of seqA_old, not this new version. There is simply no mutual recursion happening.

答案4

得分: 0

这个问题不太适合相互递归的解决方案。filter + notElem 会继续搜索超出它们能够返回结果的范围,因为它们无法利用序列严格递增的事实。

与其搜索下一个我们 没有 见过的元素,不如将问题转过来:首先假设我们将看到每个数字,并使用 delete 来剪除那些我们知道要排除的数字。

hof :: Int -> Int
hof = (!!) seqA
  where

    -- 根据定义,seqA 是另一个序列的累积和。
    seqA = scanl' (+) 1 seqB

    -- 迭代构建序列。
    seqB = unfoldr (infinitely step) (1, [2 ..])
    step c (d, xs) = (c, (c + d, delete (c + d) xs))

    -- 当 'unfoldr' 已知具有无界输入('x : xs' 总是匹配)和无界输出(我们总是返回 'Just')时的辅助函数。
    infinitely f (d, x : xs) = Just (f x (d, xs))

希望这对你有帮助。

英文:

This problem doesn’t really lend itself to a mutually recursive solution. filter + notElem will continue searching beyond where they could ever return a result, because they can’t make any use of the fact that the sequence is strictly ascending.

Rather than searching for the next element that we haven’t seen, we can turn the problem around: start by assuming we will see every number, and use delete to prune out those numbers that we know we will want to exclude.

hof :: Int -&gt; Int
hof = (!!) seqA
  where

    -- By definition, one is the cumulative sum of the other.
    seqA = scanl&#39; (+) 1 seqB

    -- Iteratively build the sequence.
    seqB = unfoldr (infinitely step) (1, [2 ..])
    step c (d, xs) = (c, (c + d, delete (c + d) xs))

    -- Helper for when ‘unfoldr’ is known to have
    -- unbounded input (‘x : xs’ always matches)
    -- and unbounded output (we always return ‘Just’).
    infinitely f (d, x : xs) = Just (f x (d, xs))

huangapple
  • 本文由 发表于 2023年2月10日 10:10:44
  • 转载请务必保留本文链接:https://go.coder-hub.com/75406297.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定