Back to Questions
1.2k
views5
comments
Lazy combinations
f#

I would like to have a sequence of combinations.

A way to generate combinations is for example

let comb n l =
let rec comb l c =
if( List.length c = n) then [c] else
match l with
| [] -> []
| (h::t) -> (comb t (h::c))@(comb t c)
in
comb l []

How do I have to transform this snippet to get a
lazy collection of combinations?

Thanks.

.

It depends on what you mean by a "lazy collection". To get a sequence of results (which will be evaluated on demand, but not cached/memoized), you can do this:

1
2
3
4
5
6
7
8
9

let comb n l =
  let rec comb l c =
    seq {
      if( List.length c = n) then yield c else
      match l with
      | [] -> ()
      | (h::t) -> yield! comb t (h::c); yield! comb t c }
  in
    comb l []
By on 12/9/2009 1:07 PM ()

That's wonderful.

let L = [1;2;3;4]

for n in 1 .. (List.length L) do
let C = comb n L
Seq.iter (printfn "%A") C

gives exactly what I want:

[1]
[2]
[3]
[4]
[2; 1]
[3; 1]
[4; 1]
[3; 2]
[4; 2]
[4; 3]
[3; 2; 1]
[4; 2; 1]
[4; 3; 1]
[4; 3; 2]
[4; 3; 2; 1]

With Maple I write

L := {1,2,3,4};
for n from 1 to nops(L) do
for C in choose(L, n) do print(C) od;
od;

(By the way, Maple gives for example {1,2,3} and
not {3,2,1}. Is there an easy way to repair this?)

If I change in Maple

print(C) to print(add(i,i=C))

I get the sum of the lists. However,

for n in 1 .. (List.length L) do
let C = comb n L
Seq.iter (printfn "%d" (List.sum C)) C

does not work.

Thank you very much for your help.

By on 12/9/2009 3:08 PM ()

The easiest way to get the lists in the opposite order is to use 

1

yield List.rev c

instead of yield c.

As to your other issue, the problem is that Seq.iter expects to be passed a function of type 'a->unit [edited; used to misread "unit->unit"], but

1

printfn "%d" (List.sum C)

doesn't have that type. In fact, this expression doesn't type check at all because C is a sequence of lists, whereas List.sum expects to take just a list. Even if C were just a list, the printfn expression would have the type unit, rather than 'a -> unit (because you are applying the printing function to a value).There are a few ways to fix this. You could replace the code I mentioned above with this:

1

fun item -> printfn "%d" (List.sum item)

to create a function that does what you want. Alternatively, you could use "point free style" to compose the printfn "%d" and List.sum functions without introducing an explicit argument:

1

List.sum >> printfn "%d"

or

1

printfn "%d" << List.sum

You can also use a similar trick to eliminate your use of the temporary variable C using the forward pipeline operator |>. This would probably be more idiomatic, and is the reason that Seq.iter's last argument is the sequence, rather than its first argument.

1
2
3

for n in 1 .. (List.length L) do
    comb n L
    |> Seq.iter (List.sum >> printfn "%d")
By on 12/9/2009 4:18 PM ()

That's wonderful.

Now, let's say I have a consumer function:

let consumeCombi item =
let s = List.sum item
printfn "list: %A sum: %d" item s

for n in 1 .. (List.length L) do
comb n L
|> Seq.iter (fun item -> consumeCombi item)

This works fine ... but, if I add another line

let consumeCombi item =
let s = List.sum item
printfn "list: %A sum: %d" item s
s = 7

which is to be interpreted as: "I have found what I was
looking for, please do not send me further combinations."
Then the compiler will not accept this ("This expression
was expected to have type unit but here has type bool.")
How, and this is now the question, can the consumer function
tell 'Seq.iter' to finish his job?

Thank you very much for your help.

By on 12/9/2009 4:57 PM ()

Seq.iter takes an argument of type 'a -> unit (that is, a function that takes an argument of some type 'a and returns no value), and applies it to each item in the sequence in turn. This obviously isn't the behavior you want, so you'll need to use another function to do what you want. There are several functions that do something like what you want. Seq.find will return the first item satisfying a predicate, and is probably what you're looking for. Seq.takeWhile will return a new sequence which is the prefix of the sequence you pass containing all items up to (but not including) the first item not satisfying a predicate.

By on 12/9/2009 5:25 PM ()

    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