Haskell, list of natural number

Question

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]

Granddad

You might be confused about the difference between () and [], since your last example works (for infinite lists) if you replace all the [] by (). – Cruel

Answer 1

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 (*)

Blackmail

Answer 2

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

Internationalist

or also nat = 1 : map succ nat – Estuarine

Answer 3

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]

Urger

Answer 4

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 :)

Pagandom

Answer 5

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.

Morven

nat n a = nat (n-k) (nat k a) where k = (n-1) == nat n a = nat (n-(n-1)) (nat (n-1) a) == nat n a = nat 1 (nat (n-1) a) == nat n a = 1 : nat (n-1) a. so naturals n == take n (repeat 1). – Trussell

or == [ 1 | _ <- [1..n] ]. to take its partial sums (or prefix sums), is usually done with tail . scanl (+) 0 of that. if you want to use sum, it can be done with map sum . tail . inits or reverse . map sum . init . tails which will only work for finite lists, but the repeated summing will make it quadratic. scanl (+) is linear. – Trussell

Thank you @WillNess. Always attentive :-) What do you mean by quadratic and linear? Something to do with execution speed? I will try to be more sophisticated in the future (although it's hard, because I don't always know where I'm heading). – Morven

that's standard terms in algorithmic complexity. execution time growing as a square of the problem size is quadratic, written O(n^2) (or maybe Theta(n^2)). and linear is linear, ~ n. there's also the first link in my profile blurb. :) – Trussell

as for sophistication, I really can't understand how your sof function is working. – Trussell

The sof function (short for "sum of") takes every two numbers, whether the tail is empty or not, keeps the first one intact and adds the second to the former, but since it gets called upon its result until the tail is exhausted, the addition between the first and second numbers is kept intact, while the third gets added to it in the following place (and so on). I hope that I've made myself clear. I taught myself how to avoid redundancy by calling empty lists, singletons and then every two numbers, whether the tail is empty or not. – Morven

your definitions are actually just the following code in disguise: naturals n | n <= 0 = [] ; naturals n = 1 : naturals (n-1) and sumOf [] = [] ; sumOf [x] = [x] ; sumOf (x:y:zs) = x : sumOf ((x+y):zs). your a never changes, in both definitions. it is always just [], and can be just omitted. you can see the transformations here. :) transforming the sof was not trivial, required a proof by induction. – Trussell

Answer 6

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.

Pacheco

This could be more compactly written naturals = 0 : map succ naturals. This kind of approach can certainly make sense in some applications, but here there is no benefit over a simple iterate. Mapping a simple operation again and again over a list is generally a bad idea, better to apply the composition over the list just once (more cache friendly). Though, I actually don't see much performance difference. – Universalism