CODEWITHSUNDEEP
haskell
Stephane Rolland
Stephane Rolland

Reputation: 39916

What is the pattern for mathematic sequence?

I'm stuck to Problem 2 of Project Euler, which makes use of the fibonnacci sequence.

My first naive implementation was grounded on the sheer math definition, using a recursive function:

fibonnacci_coefficient :: (Eq a, NUm a) => a -> a
fibonnacci_coefficient n
    | n == 0 = 1
    | n == 1 = 2
    | otherwise = fibonnacci_coefficient (n-1) + fibonnacci_coefficient (n-2)

The exercise is asking to sum the even coefficients, those not exceeding 4,000,000. When I launched my algorithm it took more than 45 minutes so I canceled it. I guess it's because of my using this function that depends for each steps on re-computing former element recursively.

Among my readings I happened to see an 'efficient' definition of the fibonnacci sequence:

fib = 1 : 2 : [ a+b | (a,b) <- zip fib (tail fib)]

Honestly, I feel, I see why it works. I see, I kind of understand, but I cannot intuitively switch from the math definition directly to such an Haskell definition.

As I understood, efficiency relies in the main concept to define a list that chases its tail. But I can't grasp the pattern. And to understand I think I need to see the whole pattern:

Given a math sequence, that depends on k indexes, let's say k=4, given function f that takes 4 arguments:

u(n) = f (u(n-1)) (u(n-2)) (u(n-3)) (u(n-4))

What would be the Haskell pattern to express this list as an infinite list / sequence?

Upvotes: 1

Views: 224

Answers (3)

&#216;rjan Johansen
&#216;rjan Johansen

Reputation: 18189

It was mentioned that it is not easy to write such a function that works for all k simultaneously. This is true if you want it to be type safe in the number of arguments. However, if you are willing to let your function f take a list of arguments instead, then it is possible (stealing the function name from @bheklilr):

import Data.List (tails)

recSeqK :: Int -> ([a] -> a) -> [a] -> [a]
recSeqK k f firstN = l where
    l = firstN ++ map (f . reverse . take k) (tails l)

fib = recSeqK 2 sum [1,2]

main = print $ take 50 fib

Note that the reverse is only needed because it is easier to write this with the opposite argument order for f of the one in the question.

Upvotes: 3

Zeta
Zeta

Reputation: 105905

There's a function in Prelude called iterate which enables you to define an infinite sequence based on repeated application:

-- example: natural numbers
nats :: [Integer]
nats = iterate (+1) 0

iterate is implemented as

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

How does this work? Well, we use the current value as new element for our resulting list, and call iterate again with f x as new current value. We can use this pattern to define other iterate variants with more arguments:

iterate2 :: (a -> a -> a) -> a -> a -> [a]
iterate2 f x y = x : iterate2 f y (f x y)

iterate3 :: (a -> a -> a -> a) -> a -> a -> a -> [a]
iterate3 f x y z = x : iterate3 f y z (f x y z)

iterate4 :: (a -> a -> a -> a -> a) -> a -> a -> a -> a -> [a]
iterate4 f a b c d = a : iterate4 f b c d (f a b c d)

-- and so on
-- example:
fibs :: [Integer]
fibs = iterate2 (+) 0 1

-- note: arguments of f are from last to first, so
--       we need to reverse the order of arguments
u = iterate4 (\a b c d -> f d c b a) x y v w

However, as you can see, the stepping function has another type, depending on how many previous values we want to use. That's also the reason we have zipWith, zipWith3, zipWith4 and so on. While it is possible to create a typeclass in order to create a single function for a fixed number of instances, it isn't possible to do this for arbitrary sequences.

That being said, you're probably good with one of those simple functions.

Upvotes: 2

jwodder
jwodder

Reputation: 57590

Assuming the first four elements of the sequence are a,b,c,d, then u(n) = f(u(n-1), u(n-2), u(n-3), u(n-4)) can be translated into a recursively-defined list in Haskell with:

u = a : b : c : d : zipWith4 f (tail (tail (tail u))) (tail (tail u)) (tail u) u

Upvotes: 3

Related Questions