CODEWITHSUNDEEP
haskellrecursion
yogsototh
yogsototh

Reputation: 15051

create an infinite recursive list in haskell using a function returning a sublist

I am trying to resolve a project euler question. I want to create the list of element in an integer spiral.

I have the function:

next_four_numbers last size = map (\p -> last + p*(size-1)) [1,2,3,4]

I certainly have other means to generate it, but in the end I want to have the infinite sequence:

diagonal_spiral_numbers = [1,3,5,7,9,13,17,21,25,31,37,43,49...]

How could I end up creating this infinte sequence using my "next_four_numbers" function? Of course I want it to be able to map this efficiently (I'd like to be able to do this for example):

take 20000 ( filter is_prime diagonal_spiral_numbers )

Thanks,

ps: of course I am learning haskell and it might be easier than I imagine.

Upvotes: 2

Views: 2607

Answers (4)

Jonathan
Jonathan

Reputation: 2203

Notice that your last and size parameters are always of the form (2x+1)^2 and 2x+3, respectively (for x in 0,1,2,3,...)

You just need to call next_four_numbers once with each of these parameters. This can be accomplished with a list comprehension:

diagonals = [next_four_numbers ((2*x+1)*(2*x+1)) (2*x+3) | x <- [0..]]

Or with a map (if you're more comfortable with that):

diagonals = map (\x -> next_four_numbers ((2*x+1)*(2*x+1)) (2*x+3)) [0..]

Then it's just a matter of flattening the list and prepending 1:

actual_diagonals = 1:concat diagonals
main = print (take 20 actual_diagonals)

This can probably be cleaned up a bit, but I'll leave that to you ;) BTW, [0..] is just shorthand for the infinite list 0,1,2,3,...

Upvotes: 0

J.Q. Public
J.Q. Public

Reputation: 1

It certainly can be done that way, generating a list of lists and then flattening it (check out the concatMap function), but the usual way is to have your helper function take an additional "tail" argument, and then return a:b:c:d:tail.

Another approach would be to use zipWith3.

Upvotes: 0

interjay
interjay

Reputation: 110069

If you have a function that generates the next state based on the previous one, you can then use the iterate function to create the entire list. In this case, the state consists of the four numbers and the size. After calling iterate, I call map fst to get rid of the size values, and concat to concatenate all the lists.

nextState (prev,size) = (next_four_numbers (last prev) size, size+2)
allNums = concat $ map fst $ iterate nextState ([1],3)

Upvotes: 4

peoro
peoro

Reputation: 26060

You could do it like this:

diagonal_spiral_numbers =
    let helper l s =
            let next_four_numbers last size = map (\p -> last + p*(size-1)) [1,2,3,4]
                (a:b:c:d:[]) = next_four_numbers l s
            in  a:b:c:d : helper d (s+2)
    in  1 : helper 1 3

Here the output:

take 20 diagonal_spiral_numbers
[1,3,5,7,9,13,17,21,25,31,37,43,49,57,65,73,81,91,101,111]

However I'm wondering why you need to use your next_four_numbers functions: the resulting list could be generated in many simpler (and I'd say overall better) ways.

Upvotes: 1

Related Questions