Back to Questions
4.1k
views12
comments
Best way to express this?
f#

I have 3 LazyLists of numbers, each representing some sequence. For simplicity we can just assume they're in a normal list. All 3 are sorted in ascending order. I want to generate every single number that can be obtained by choosing one element from each of the 3 lists and multiplying them together. I only want to keep numbers where the product is less than some fixed constant N, and since there are potentially a huge amount of numbers in each list and they get very large, I want to stop immediately as soon as I know that every future product is guaranteed to be larger than N. Also, the same number might appear in more than one of the lists, and if that happens I want to skip that combination.

The resulting products can be stored in a Set, HashSet, List, doesn't matter as long as there are no duplicates. I came up with something, but it's absolutely horrendous looking, and I'm having a lot of difficulty expressing this in a way that isn't horrendous. In C++ or something it would be really simple, I could just do this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

for (int i=0; i < list1_count; ++i)
{
   for (int j=0; j < list2_count; ++j)
   {
      if (l2 [ j] == l1 [ i]) continue;

      int temp = l1 [ i] * l2 [ j];
      if (temp >= N) break;

      for (int k=0; k < list3_count; ++k)
      {
         if (l3 [ k] == l2 [ j] || l3 [ k] == l1 [ i]) continue;

         int temp2 = temp*l3 [ k];
         if (temp2 >= N) break;
         set.add(temp*temp2);
      }
   }
}

But I'm having some difficulty writing this same code in F#. If they were stored in an array, I could use imperative code to basically mimic the above with mutable index variables, but with lists the combination of breaks, continues, and duplicate checking is making this a little difficult.

.

Yeah, F# is poor at break and continue. You goaded me into authoring them, though:

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
38
39
40
41
42
43
44
45
46
47

#light
// Author a continuation monad to provide non-local control flow
type ContinuationBuilder() = 
    member this.Return(x) = (fun k -> k x) 
    member this.Let(x,f) = f x 
    member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
    member this.Delay(f) = (fun k -> f () k)
    member this.Combine(m1,m2) = this.Bind(m1, fun() -> m2)
    member this.Zero() = (fun k -> k())
    member this.Execute(m) = m id
    member this.CallCC(f) = (fun origK -> f origK origK)
let K = new ContinuationBuilder()
// Define a C-style "for" loop
let CStyleFor init test update body =
    K.CallCC (fun origK -> K {
        init()
        let _break = (fun k -> origK ())
        let rec TestBodyLoop = K {
            if test() then
                do! body _break _continue
                do! _continue }
        and _continue = K {
            update()
            do! TestBodyLoop }
        do! TestBodyLoop })
let i = ref 0
let a = [| 0 .. 10 |]
(*
for(i = 0; i < 10; ++i) {
    printf("n=%d", a[ i]);
    if (i==2)
        continue;
    printf("once again, n=%d", a[ i]);
    if (i==4)
        break;
    printf("once more, n=%d", a[ i]);
}
*)
K.Execute(K { do! CStyleFor (fun()-> i:=0) (fun()-> !i<10) (fun()-> i:=!i+1) (fun _break _continue -> K {
    printfn "n=%d" a.[!i]
    if !i = 2 then
        do! _continue
    printfn "once again, n=%d" a.[!i]
    if !i = 4 then
        do! _break
    printfn "once more, n=%d" a.[!i]
})})
By on 3/6/2009 11:14 PM ()

I have to admit, I have no idea how this code works :) What chapter(s) in Expert F# discusses such techniques? Or if you have external links that discuss techniques such as this I'd be interested.

Also, is there a technical limitation that prevents F# from supporting break/continue? It seems like even if break/continue could not be supported, it would still be easily achievable if the for looping construct supported more advanced expressions. For example,

1
2
3
4

for (i in 1..10) && (not stop) do
    if ( i * product_so_far > N) then stop := true
    else if (not already_seen_this_i) then
        //do stuff

Would express one of the loops, and you could nest similar blocks inside of each other to achieve the desired result.

By on 3/7/2009 5:25 PM ()

I have to admit, I have no idea how this code works :) What chapter(s) in Expert F# discusses such techniques? Or if you have external links that discuss techniques such as this I'd be interested.

Also, is there a technical limitation that prevents F# from supporting break/continue? It seems like even if break/continue could not be supported, it would still be easily achievable if the for looping construct supported more advanced expressions. For example,

1
2
3
4

for (i in 1..10) && (not stop) do
    if ( i * product_so_far > N) then stop := true
    else if (not already_seen_this_i) then
        //do stuff

Would express one of the loops, and you could nest similar blocks inside of each other to achieve the desired result.

The same can be expressed more functionally as

1
2
3
4

1..10
|> Seq.takeWhile((*) product_so_far >> (<) N)
|> Seq.filter(fun _ -> not already_seen_this_i)
|> Seq.iter(fun i -> (*do stuff*))
By on 3/3/2010 12:16 PM ()

Actually you need to be careful with composition and (<) and (>). I believe you mean:

1
2
3
4

1..10
|> Seq.takeWhile((*) product_so_far >> (<b>></b>) N)
|> Seq.filter(fun _ -> not already_seen_this_i)
|> Seq.iter(fun i -> (*do stuff*))

That is, 

1

N (>) product_so_far

:-)

By on 3/8/2010 2:10 AM ()

That is, 

1

N (>) product_so_far

:-)

Well, is that the code divisortheory posted ;) ?

By on 3/8/2010 9:30 AM ()

That is, 

1

N (>) product_so_far

:-)

Well, is that the code divisortheory posted ;) ?

mau was responding to eventhelix, who uses (<) instead of (>). It's easy to confuse these when chaning infix to prefix.

By on 3/8/2010 9:41 AM ()

mau was responding to eventhelix, who uses (<) instead of (>).

And that's correct, isn't it? eventhelix preserved the semantics of divisortheory's code, whereas mau flipped it by not flipping the operator.
So yes, I wholeheartedly agree with you. As long as F# doesn't support operator sections, it's not worth the hassle and confusion.

By on 3/10/2010 10:10 AM ()

I borrowed the syntax from J for this kind of situation:

1
2
3
4
5

 

let (&.) f x = fun y -> f y x
let lessthan3 = (<)&.3

it is '<&3' in J but '&' is taken and the () is needed for '<'

By on 3/8/2010 6:28 PM ()

In the interest of preferring sanity to obfuscation, might I suggest that

1

    (fun x -> x < MAX)

is better than

1
2
3
4

(>) MAX
(flip << (<)) MAX
(<) &. MAX
etc.
By on 3/8/2010 9:14 PM ()

In the interest of preferring sanity to obfuscation, might I suggest that

1

(fun x -> x < MAX)

is better than

1
2
3
4

(>) MAX
(flip << (<)) MAX
(<) &. MAX
 etc.

I used to incline to think in this way but after spending some time with these seemingly like line noise(in J) and also the frequently used flip, circle( f.g) point free style in Haskell, I do think there are advantages.

The analogy is a bit like English vs Chinese.

By on 3/8/2010 10:58 PM ()

I very nearly have no idea how it works either. :) I just use [link:www.haskell.org] and some intuition; my brain knows how to tell my fingers to type this code, but is hasn't yet let me in on what the heck is going on. :)

I don't think there are necessarily any technical limitations; 'break' and 'continue' are reserved words, so I imagine some future version of the language will support them, it's just a matter of priorities. (I am not sure if/how the keywords would interact with the computation expression 'builder' methods 'For' and 'While'.)

By on 3/7/2009 8:20 PM ()

Hi,
Just as a side-note, I implemented a more syntactically pleasant version of the computation expression builder that let's you write 'break' and 'continue' in F#. This downside is that it is a computation expression, which is translated into member calls that take lambda functions as arguments, so it probably won't be very efficient.

However, if you're looking for a nice way to write this, you can take a look at it :-). The code would look like this:

1
2
3
4
5
6
7
8
9
10
11

imperative {
  for i in 0 .. (list1_count - 1) do
    for j in 0 .. (list2_count - 1) do
      if (l2.[j] = l1.[ i]) then do! continue
      let temp = l1.[ i] * l2.[ j]
      if (temp >= N) then do! break
      for k in 0 .. (list3_count - 1) do
         if (l3.[ k] = l2.[ j] || l3.[ k] = l1.[ i]) do! continue
         let temp2 = temp*l3.[ k]
         if (temp2 >= N) then do! break
         set.add(temp*temp2) }

Here are links to the article that describes this:

By on 4/25/2009 7:50 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