英文:
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
一个初始值,并在之后重新定义seqA
和seqB
,它似乎可以正常工作。不过我注意到,将较大的值传递给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。如果它发现x
是seqA
的第一个元素,那很好:它可以返回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 (<= 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 -> [Integer] -> [Integer]
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
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:
> 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 -> [Integer] -> [Integer]
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
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:
> 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> a = 1
ghci> b = [a]
ghci> b
[1]
a
只是1
的名称,b
只是[1]
的名称。后者是通过查看a
是一个名称的值来计算的,但它绝对是值[1]
,而不是表达式[a]
,b
引用的。
ghci> a = 2
ghci> b
[1]
执行a = 2
不会改变a
引用的值,它只会改变ghci提示符中可用的环境状态。这不会影响a
是名称为1时计算的任何值;它们是纯粹的值,且保持不变。
一个简单的思考方式是,a = 2
不是“改变a
”,它只是引入了一个新的、独立的绑定。因为它恰好与现有绑定同名,新绑定遮蔽了旧绑定,使你无法在以后的表达式中引用旧绑定。但旧绑定没有发生任何变化。
实际上,在编译模块中,在可以为一个名称有多个绑定的上下文中,你将看到完全相同的行为(如果你使用let
遮蔽函数参数,或嵌套let
等)。除了一个绑定之外,所有其他绑定都将无法访问,但在阴影绑定的定义中使用的内容保持完全不变;它们不会重新评估,就好像它们是在新绑定中定义的一样。
因此,考虑到这一点,很容易解释为什么这样工作:
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
这与如果你这样定义它是大致相同的:
ghci> seqB_old = [2, 4, 5, 6]
ghci> seqA_old = 1 : zipWith (+) seqA_old seqB_old
ghci> seqB_new = 2 : filter (`notElem` seqA_old) [3..]
ghci> seqA_new = 1 : zipWith (+) seqA_new seqB_new
ghci> hof = (!!) seqA_new
seqB_old
只是一个有限列表。- 因为
zipWith
在最短列表的长度处停止,seqA_old
也只是一个有限列表,尽管它是根据自身定义的。 seqB_new
是一个无限列表,只需要过滤每个元素与有限列表seqA_old
的任何元素。这不会陷入amalloy指出的问题,但实际上并不是你试图定义的正确列表。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> a = 1
ghci> b = [a]
ghci> 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> a = 2
ghci> 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 let
s, 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> 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
It's much the same as if you had defined it this way:
ghci> seqB_old = [2, 4, 5, 6]
ghci> seqA_old = 1 : zipWith (+) seqA_old seqB_old
ghci> seqB_new = 2 : filter (`notElem` seqA_old) [3..]
ghci> seqA_new = 1 : zipWith (+) seqA_new seqB_new
ghci> hof = (!!) seqA_new
seqB_old
is just a finte list- 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. seqB_new
is an infinite list that just has to filter each element against any of the elements of the finite listseqA_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 defineseqA_new
is defined in terms of itself, butseqB_new
was defined in terms ofseqA_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 -> Int
hof = (!!) seqA
where
-- By definition, one is the cumulative sum of the other.
seqA = scanl' (+) 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))
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论