3.5k
views 12
comments

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:

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:

#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 brianmcn on 3/6/2009 11:14 PM (permalink)

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,

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 divisortheory on 3/7/2009 5:25 PM (permalink)

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,
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..10
|> Seq.takeWhile((*) product_so_far >> (<) N)
|> Seq.filter(fun _ -> not already_seen_this_i)
|> Seq.iter(fun i -> (*do stuff*))

By eventhelix on 3/3/2010 12:16 PM (permalink)

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

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,

N (>) product_so_far

:-)

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

That is,
N (>) product_so_far
:-)

Well, is that the code divisortheory posted ;) ?

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

That is,
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 brianmcn on 3/8/2010 9:41 AM (permalink)

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 Kha on 3/10/2010 10:10 AM (permalink)

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

 

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 gary on 3/8/2010 6:28 PM (permalink)

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

    (fun x -> x < MAX)

is better than

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

By brianmcn on 3/8/2010 9:14 PM (permalink)

In the interest of preferring sanity to obfuscation, might I suggest that
(fun x -> x < MAX)
is better than
(>) 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 gary on 3/8/2010 10:58 PM (permalink)

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 brianmcn on 3/7/2009 8:20 PM (permalink)

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:

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 Tomas Petricek on 4/25/2009 7:50 AM (permalink)

Topic tags

Built with WebSharper

Home

Answers

Events

Courses

Groups and Conferences

Blogs

Jobs

Developers

Topic tags