CODEWITHSUNDEEP
listhaskellstreamlazy-evaluation
Hellnar
Hellnar

Reputation: 64793

Haskell, list of natural number

I am an absolute newbie in Haskell yet trying to understand how it works.

I want to write my own lazy list of integers such as [1,2,3,4,5...].

For list of ones I have written

ones = 1 : ones

and when tried, works fine:

*Main> take 10 ones
[1,1,1,1,1,1,1,1,1,1]

How can I do the same for increasing integers ?

I have tried this but it indeed fails:

int  = 1 : head[ int + 1]

And after that how can I make a method that multiplies two streams? such as:

mulstream s1 s2 = head[s1] * head[s2] : mulstream [tail s1] [tail s2]

Upvotes: 13

Views: 20805

Answers (6)

Antonielly
Antonielly

Reputation: 71

For completeness, here is another technique equivalent to [0..] for generating an infinite stream of natural numbers:

naturals = 0 : allthefollowingnat naturals where
    allthefollowingnat (current : successors) = immediateSuccessor : allthefollowingnat successors where
        immediateSuccessor=current+1

While this technique is arguably overkill for generating a stream of natural numbers, it follows a template that is useful for defining various streams where the next values depend on previous ones. For instance, here is a Fibonacci stream, defined by using the as-pattern (@):

fibstream = 0 : 1 : allthefollowingfib fibstream where
    allthefollowingfib (previous : values@(current : _)) = next : allthefollowingfib values where
        next = current+previous

As another example that follows the same template, let's define a stream of «index, factorial» pairs:

facstream = (0, 1) : allthefollowingfac facstream where
    allthefollowingfac ((currentIndex, currentFac) : others) = (successorIndex, nextFac) : allthefollowingfac others where
        successorIndex = currentIndex + 1
        nextFac = successorIndex*currentFac

Mathematically, this template, expressed in a generalized fashion, is a homomorphism having the following structure:

g (x1:x2:...:xn:xs) = (f x1 x2 ... xn):(g x2:...:xn:xs),

where g is a function over a list, and f is a function over element(s) of that list.

Upvotes: 0

Marco_O
Marco_O

Reputation: 111

You can define a list of ones up to a certain number and then sum the first to the second by keeping the former intact (and so on) like this:

ones :: Integer -> [Integer]
ones n
  | n <= 0    = []
  | otherwise = one n []
    where
      one 1 a = (1:a)
      one n a = one (n-k) (one k a)
        where
          k = (n-1)

sumOf :: [Integer] -> [Integer]
sumOf l = sof l []
  where
    sof [] a = a
    sof (x:[]) a = (x:a)
    sof (x:y:zs) a = sof (x:a) (sof ((x+y):zs) a)

Since they're all ones, you can increment them in any way that you feel like, from left to right, to a middle point and so on, by changing the order of their sum. You can test this up to one hundred (or more) by using:

(sumOf . ones) 100

Edit: for its simplification, read the comments below by Will Ness.

Upvotes: 1

Hiato
Hiato

Reputation: 161

I'm not sure if this is what you were asking, but it would seem to me that you wanted to build a list of increasing natural numbers, without relying on any other list. So, by that token, you can do things like

incr a = a : inrc (a+1)
lst = inrc 1

take 3 lst
=> [1,2,3]

That, technically, is called an accumulating function (I believe) and then all we did is make a special case of it easily usable with 'lst'

You can go mad from there, doing things like:

lst = 1 : incr lst where incr a = (head a) + 1 : incr (tail a)

take 3 lst
=> [1,2,3]

and so on, though that probably relies on some stuff that you wont have learned yet (where) - judging by the OP - but it should still read pretty easily.

Oh, right, and then the list multiplication. Well, you can use zipWith (*) as mentioned above, or you could reinvent the wheel like this (it's more fun, trust me :)

lmul a b = (head a * head b) : lmul (tail a) (tail b) 
safemul a b  
  | null a || null b  =  []
  | otherwise
         = (head a * head b) : safemul (tail a) (tail b)

The reason for safemul, I believe, you can find out by experimenting with the function lmul, but it has to do with 'tail' (and 'head' as well). The trouble is, there's no case for an empty list, mismatched lists, and so on in lmul, so you're either going to have to hack together various definitions (lmul _ [] = []) or use guards and or where and so on ... or stick with zipWith :)

Upvotes: 5

clord
clord

Reputation: 338

There is syntax for this in the langauge:

take 10 [1,2..]

=> [1,2,3,4,5,6,7,8,9,10]

You can even do different strides:

take 10 [1,3..]
=> [1,3,5,7,9,11,13,15,17,19]

Upvotes: 5

sepp2k
sepp2k

Reputation: 370112

The reasons that int = 1 : head [ int + 1] doesn't work are:

  • head returns a single element, but the second argument to : needs to be a list.
  • int + 1 tries to add a list and a number, which isn't possible.

The easiest way to create the list counting up from 1 to infinity is [1..]

To count in steps other than 1 you can use [firstElement, secondElement ..], e.g. to create a list of all positive odd integers: [1, 3 ..]

To get infinite lists of the form [x, f x, f (f x), f (f (f x)),...] you can use iterate f x, e.g. iterate (*2) 1 will return the list [1, 2, 4, 16,...].

To apply an operation pairwise on each pair of elements of two list, use zipWith:

mulstream s1 s2 = zipWith (*) s1 s2

To make this definition more concise you can use the point-free form:

mulstream = zipWith (*)

Upvotes: 21

Łukasz Lew
Łukasz Lew

Reputation: 50258

For natural numbers you have to use map:

num1 = 1 : map (+1) num1

Or comprehensions:

num2 = 1 : [x+1 | x <- num2]

Or of course:

num3 = [1..]

Upvotes: 21

Related Questions