2 people like it.
Like the snippet!

Gluing-up sequence members

While thinking on Project Euler Problem 40 solution (http://projecteuler.net/index.php?section=problems&id=40) the following subproblem has surfaced: how to glue up string presentations of a sequence members to reach a given length of result string. The snippet gives at least 3 different implementations of such function with performance comparison; as a bonus a solution to Problem 40 is given.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37:

open System
open System.Text

(Performance measurement instrumentation)

// Glue up using Seq.collect (worst peformer)
let glueUp1 len ss =
    new string (
        ss
        |> Seq.collect (fun s -> Seq.ofArray <| s.ToString().ToCharArray())
        |> Seq.take len
        |> Seq.toArray)

// Glue up using Seq.scan + Seq.skipWhile
let glueUp2 len ss =
    ss
    |> Seq.scan (fun (accum: StringBuilder) s -> accum.Append(s.ToString())) (StringBuilder())
    |> Seq.skipWhile (fun x -> x.Length < len)
    |> Seq.head |> string |> fun x -> x.Substring(0, len)

// Glue up using Seq.pick and a closure over StringBuilder (best performer)
let glueUp3 len ss =
    let glue len =
        let accum = StringBuilder()
        fun item ->
            if accum.Length >= len then
                Some(accum.ToString())
            else
                accum.Append(item.ToString()) |> ignore
                None
    
    ss
    |> Seq.pick(glue len) |> fun x -> x.Substring(0, len)

(Performance measurement)

(Project Euler Problem 40 Solution)

namespace System

namespace System.Text

let time f x =
    let t = new System.Diagnostics.Stopwatch()
    t.Start()
    try
        f x
    finally
        printf "Took %dms\n" t.ElapsedMilliseconds

val glueUp1 : len:int -> ss:seq<'a> -> string

Full name: Script.glueUp1

val len : int

val ss : seq<'a>

Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string

module Seq

from Microsoft.FSharp.Collections

val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect

val s : 'a

val ofArray : source:'T [] -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.ofArray

Object.ToString() : string

val take : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.take

val toArray : source:seq<'T> -> 'T []

Full name: Microsoft.FSharp.Collections.Seq.toArray

val glueUp2 : len:int -> ss:seq<'a> -> string

Full name: Script.glueUp2

val scan : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> seq<'State>

Full name: Microsoft.FSharp.Collections.Seq.scan

val accum : StringBuilder

Multiple items
type StringBuilder =
  new : unit -> StringBuilder + 5 overloads
  member Append : value:string -> StringBuilder + 18 overloads
  member AppendFormat : format:string * arg0:obj -> StringBuilder + 4 overloads
  member AppendLine : unit -> StringBuilder + 1 overload
  member Capacity : int with get, set
  member Chars : int -> char with get, set
  member Clear : unit -> StringBuilder
  member CopyTo : sourceIndex:int * destination:char[] * destinationIndex:int * count:int -> unit
  member EnsureCapacity : capacity:int -> int
  member Equals : sb:StringBuilder -> bool
  ...

Full name: System.Text.StringBuilder

--------------------
StringBuilder() : unit
StringBuilder(capacity: int) : unit
StringBuilder(value: string) : unit
StringBuilder(value: string, capacity: int) : unit
StringBuilder(capacity: int, maxCapacity: int) : unit
StringBuilder(value: string, startIndex: int, length: int, capacity: int) : unit

StringBuilder.Append(value: char []) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: obj) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: uint16) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: decimal) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: float32) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int64) : StringBuilder
   (+0 other overloads)
StringBuilder.Append(value: int) : StringBuilder
   (+0 other overloads)

val skipWhile : predicate:('T -> bool) -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skipWhile

val x : StringBuilder

property StringBuilder.Length: int

val head : source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.head

val x : string

String.Substring(startIndex: int) : string
String.Substring(startIndex: int, length: int) : string

val glueUp3 : len:int -> ss:seq<'a> -> string

Full name: Script.glueUp3

val glue : (int -> 'b -> string option)

val item : 'b

union case Option.Some: Value: 'T -> Option<'T>

StringBuilder.ToString() : string
StringBuilder.ToString(startIndex: int, length: int) : string

val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore

union case Option.None: Option<'T>

val pick : chooser:('T -> 'U option) -> source:seq<'T> -> 'U

Full name: Microsoft.FSharp.Collections.Seq.pick

time (glueUp1 1000000) (Seq.initInfinite(fun x -> x)) |> ignore
time (glueUp2 1000000) (Seq.initInfinite(fun x -> x)) |> ignore
time (glueUp3 1000000) (Seq.initInfinite(fun x -> x)) |> ignore

// Project Euler Problem 40
let digits = Seq.initInfinite (fun n -> n) |> glueUp2 1000001
[1;10;100;1000;10000;100000;1000000]
|> List.fold (fun result x -> result * Int32.Parse(string digits.[x])) 1
|> printfn "Project Euler Problem 40 Answer: %d"

Raw view Test code New version

More information

Link:	http://fssnip.net/8a
Posted:	13 years ago
Author:	Gene Belitski
Tags:	sequences , project euler