Yielding from inside a lambda expression in F#

Question

I've implemented a standard mutable in-place permutations algorithm in F# (if there's some built-in way of doing something similar, I'd be grateful for the information):

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n =
        if n = alphabet.Length
        then f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                permutations' (n+1)
                swap n i
    permutations' 0

Although the function is quite versatile I was wondering if there was some way in F# to implement a wrapper function that would yield me the discovered items as a sequence. Something resembling the following (incorrect) F# method:

let permutations_seq (alphabet:'a array) =
    seq {
        permutations (fun arr -> yield arr.Clone()) alphabet
    }

In permutations I don't want to directly yield as I'd like to maintain the function general and I don't want the client to always have to pay the price for array cloning.

How would you do it?

Answer 1

If you want to "yield" results from the lambda function, then the lambda function itself needs to return a sequence (and so the caller of the lambda function needs to return a sequence too). So, there is no way to get what you want without modifying the permutations function (because you cannot yield values from code running in one (nested) scope to a list defined in some other (outer) scope).

However, you can change permutations to look something like this:

let permutations f (alphabet:'a array) =
    let swap i j =
        let aux = alphabet.[i]
        alphabet.[i] <- alphabet.[j]
        alphabet.[j] <- aux
    let rec permutations' n = seq {
        if n = alphabet.Length
        then yield! f alphabet
        else
            for i in n..(alphabet.Length-1) do
                swap n i
                yield! permutations' (n+1)
                swap n i }
    permutations' 0

I wrapped permutations' in the seq { .. } block and added yield! before f alphabet (so that all elements produced by the function f are passed as results) and I also added yield! to the recursive call.

Then you can write:

permutations (fun arr -> seq { yield arr |> Array.map id }) [|1;2;3|]

The code is using Array.map id instead of Clone so that you get a type-safe copy of the array rather than an obj as returned by the .NET cloning mechanism.

However, I suppose that you do not actually need to yield multiple items from the lambda, so you could change yield! f alphabet to just yield f alphabet (to return just a single element rather than multiple elements) and write:

permutations (fun arr -> arr |> Array.map id) [|1;2;3|]

This way, you - at least - get a nice way to abstract away the cloning behavior (and you can choose to clone or not to clone the array easily).

Answer 2

If you really want to use a call back (reactive) approach then use reactive extensions

https://github.com/fsharp/FSharp.Reactive/blob/master/src/Observable.fs

and write

let permutations (alphabet:'a array) =
    Observable.create (fun subscriber ->
      let swap i j =
          let aux = alphabet.[i]
          alphabet.[i] <- alphabet.[j]
          alphabet.[j] <- aux
      let rec permutations' n = 
          seq {
                  if n = alphabet.Length
                  then subscriber.OnNext(alphabet)
                  else
                      for i in n..(alphabet.Length-1) do
                          swap n i
                          permutations' (n+1)
                          swap n i
          }
      permutations' 0
    )

Then you can do

permutations [|"a"; "b"; "c"|]
|> Observable.map ( fun arr -> arr.Clone() )
|> Observable.ToEnumerable
|> Seq.ToList

However note the symetry with respects to the other answer I posted based on yield so you don't gain much over yield in this case.