F#: partition function like the one in Clojure

Question

Clojure has a nice function called partition which works on sequences. It breaks a given sequence into a sequence of equally long lists. The first parameter specifies the length of the fragaments. The second parameter is an offset which specifies the next start of an fragment.

(partition 3 1 (range 5))
;;=> ((0 1 2) (1 2 3) (2 3 4))

(partition 4 6 (range 20))
;;=> ((0 1 2 3) (6 7 8 9) (12 13 14 15))

(partition 4 3 (range 20))
;;=> ((0 1 2 3) (3 4 5 6) (6 7 8 9) (9 10 11 12) (12 13 14 15) (15 16 17 18))

https://clojuredocs.org/clojure.core/partition

I'm looking for an equivalent function in F#. Clearly List.partition does something else (https://msdn.microsoft.com/en-us/library/ee353782.aspx). Maybe there is a library which offers such a function?

Answer 1

In F# you have two similar functions: windowed which is like Clojure's partition but with second parameter fixed as 1 and chunkBySize with second parameter equals to the first.

You can combine both and get the desired function. Here's an example with Lists:

let partition x y = List.windowed x >> List.chunkBySize y >> List.map List.head

They're also available for arrays and sequences but note that for sequences the inner collection will be an array, which is actually a sequence. So if you want the result inferred strictly as a sequence of sequences you will have to add a conversion or upcast:

let partition x y = Seq.windowed x >> Seq.chunkBySize y >> Seq.map (Seq.head >> seq)

Answer 2

You can implement this function yourself and as demonstrated by @Gustavo this isn't too hard. One problem is if the function you just done works correctly.

So here's an implementation and property tests using FsCheck to test the properties of the partition function holds.¨

FsCheck is a great tool to check that the function you just implemented has the right properties.

open FsCheck

let partition (size : int) (increment : int) (vs : 'T []) : 'T [] [] =
  let size      = max 1 size
  let increment = max 1 increment
  let length    = vs.Length
  [| for i in [size..increment..length] -> vs.[(i - size)..(i - 1)] |]

let range (n : int) : int [] = [| 0..(n - 1) |] 

type Properties() =

  static member ``all partitions have the right size`` (size : int, increment : int, vs : int []) =
    (size > 1 && increment > 1 && vs.Length > 1) ==> 
      fun () ->
        let partitions = partition size increment vs
        // Iterates over partitions and make sure they have the same Length = size
        let rec check = function
          | i when i < 
            partitions.Length -> partitions.[i].Length = size && (check (i + 1))
          | _ -> true
        check 0

  static member ``all partitions have been incremented the right way`` (size : int, increment : int, vs : int []) =
    (size > 1 && increment > 1 && vs.Length > 1) ==>
      fun () ->
        let ivs = vs |> Array.mapi (fun i v -> (i,v))
        let partitions = partition size increment ivs
        // Iterates over partitions and make sure the first element has the right increment
        let rec check = function
          | i when i < partitions.Length -> 
            let ii, vv = partitions.[i].[0]
            ii = (i*increment) && vv = vs.[ii]  && (check (i + 1))
          | _ -> true
        check 0

  static member ``all partitions have the right content`` (size : int, increment : int, vs : int []) =
    (size > 1 && increment > 1 && vs.Length > 1) ==> 
      fun () ->
        let ivs = vs |> Array.mapi (fun i v -> (i,v))
        let partitions = partition size increment ivs
        // Iterates over partitions and make sure the each in the partition is correct element
        let rec check = function
          | i when i < partitions.Length -> 
            let partition = partitions.[i]
            let exp       = i*increment
            let rec check_partition = function
              |  i when i < partition.Length -> 
                let ii, vv = partition.[i] 
                ii = (exp + i) && vv = vs.[ii] && check_partition (i + 1)
              | _ -> true
            check_partition 0 && (check (i + 1))
          | _ -> true
        check 0

[<EntryPoint>]
let main argv = 
  range 5   |> partition 3 1 |> printfn "%A"
  range 20  |> partition 4 6 |> printfn "%A"
  range 20  |> partition 4 3 |> printfn "%A"

  let config = { Config.Quick with MaxFail = 100000; MaxTest = 1000 }

  // Generates random data and make sure the properties holds for any random data
  Check.All<Properties> config

  0

So even though you didn't ask for this I thought perhaps it's of interest to you anyway.