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!
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.