Back to Questions
1.1k
views5
comments
Seq class function to generate a sequence of powers?
f#

I want to generate a sequence of powers, eg. 1, 2, 4, 16, etc.

This works...

1
2
3
4
5
6

let Powers n p = 
    seq { let value = ref 1
          yield !value
          for i in 1..p-1 do
            value := !value * n
            yield !value }

> Powers 2 4;;
val it : seq<int> = seq [1; 2; 4; 8]

I've tried to find a Seq class function (eg. map, fold, etc) to do the same thing functionally, but can't work it out. (oh. it can be done with mapi and the power operator **, but, firstly, ** operates on floats, and, secondly, the point of the exercise is to find some way of feeding a cumulative result (the last power value) and the "n" parameter back into the sequence, similar to the imperative solution).

Any suggestions?

.

Seq.unfold.

Return None to stop or Some(x,nextState) to yield x into the result sequence and keep some new state. Thus:

1
2
3
4
5
6
7
8
9

let Powers n p =
    (0,1) |> Seq.unfold (fun (curExp,x) ->
        if curExp < p then
            let nextX = x * n
            Some(x, (curExp+1,nextX))
        else
            None)
            
printfn "%A" (Powers 2 5 |> Seq.toList)
By on 10/29/2009 8:51 PM ()

Thanks Brian! :).. Exactly what I was looking for.

btw, I like that trick for printing a sequence (to get around the lazy evaluation, and do it in one line, without a let)...

1

printfn "%A" (Powers 2  5 |> Seq.toList)

Gotta love functional programming! :)

By on 10/29/2009 9:16 PM ()

I love using Seq.unfold, but I also recommend taking a look at the scan function. It's like a fold, but keeps track of intermediate values. The function you mention would become something like this:

1

let Powers n p = Seq.init p (fun _ -> n) |> Seq.scan (*) 1

Now what does this do?
Step 1: generate a sequence of p times the value n.
Step 2: use the scan function to generate the following sequence of intemediary results: 1, 1*n, 1*n*n, ...

Example:

1
2

> Powers 3 8 |> Seq.toList;;
val it : int list = [1; 3; 9; 27; 81; 243; 729; 2187; 6561]

P.S. replace 

1

Seq.init p (fun _ -> n)

by 

1

Seq.initInfinite (fun _ -> n)

for a sequence of 'infinite' length.

P.P.S. replace the 1 at the end by 1L or 1I for powers of int64/bigints. Yay for type inference!

Okay, last edit: the following is a generic list-of-powers function that works on any type that has a concept of 1 (has a member get_One) and multiplication:

1
2

open Microsoft.FSharp.Core.LanguagePrimitives
let inline PowersGeneric n p = Seq.init p (fun _ -> n) |> Seq.scan (*) GenericOne

Example:

1
2
3
4
5
6
7
8
9

> PowersGeneric 2 8 |> Seq.toList;;
val it : int list = [1; 2; 4; 8; 16; 32; 64; 128; 256]
> PowersGeneric 2L 8 |> Seq.toList;;
val it : int64 list = [1L; 2L; 4L; 8L; 16L; 32L; 64L; 128L; 256L]
> PowersGeneric 2.0 8 |> Seq.toList;;
val it : float list = [1.0; 2.0; 4.0; 8.0; 16.0; 32.0; 64.0; 128.0; 256.0]
> PowersGeneric 2I 8 |> Seq.toList;;
val it : System.Numerics.BigInteger list =
  [1I; 2I; 4I; 8I; 16I; 32I; 64I; 128I; 256I]
By on 10/30/2009 1:43 AM ()

You can also create a numeric literal module to make generic zero and one a little more readable:

1
2
3
4
5
6

module NumericLiteralG =
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne

let inline powers n p = Seq.init p (fun _ -> n) |> Seq.scan (*) 1G
By on 10/30/2009 4:11 PM ()

Thanks, cfern - a very interesting and helpful post. The generic version is particularly interesting.

By on 10/30/2009 3:38 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper