Geeks With Blogs
Mark Pearl

 

So I have seen a few posts done by other F# fans on solving project Euler problems. They looked really interesting and I thought with my limited knowledge of F# I would attempt a few and the first one I had a look at was problem 5.

Which said : “2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?”

So I jumped into coding it and straight away got stuck – the C# programmer in me wants to do a loop, starting at one and dividing every number by 1 to 20 to see if they all divide and once a match is found, there is your solution. Obviously not the most elegant way but a good old brute force approach. However I am pretty sure this would not be the F# way….

So after a bit of research I found the Sequences and how useful they were. Sequences seemed like the beginning of an approach to solve my problem. In my head I thought - create a sequence, and then start at the beginning of it and move through it till you find a value that is divisible by 1 to 20. Sounds reasonable?

So the question is begged - how would you create a sequence that you are sure will be large enough to hold the solution to the problem? Well… You can’t know!

Some more googling and I found what I would call infinite sequences – something that looks like this…

let nums = 1 |> Seq.unfold (fun i -> Some (i, i + 1))

 

My interpretation of this would be as follows… create a sequence, and whenever it is called add 1 to its size (I would appreciate someone helping me on wording this right functionally).

Something that I don’t understand fully yet is the forward pipe operator (|>) which I think plays a key role in this code.

With this in hand I was able to code a basic optimized solution to this problem. I’m going to go over it some more before I post the full code just in case!

Posted on Tuesday, April 13, 2010 5:55 PM F# | Back to top


Comments on this post: F# and the useful infinite Sequence (I think)

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
the '1' is the 'starter'

1 |> Seq.unfold (...)

<=>

Seq.unfold (...) 1

check the unfold signature and you would know why. Also search 'currying/partial application' in google if you want to learn the behaviour of F#. this is one of the few thing most people from other language background find puzzling as only a handful of language has auto-currying/partial applicaton. One of the top feature I like about F#.
Left by gary on Apr 13, 2010 8:03 PM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
I haven't played with F# since the CTP, but I think an infinite sequence is great way to attack this problem. I recently blogged about a real world application for an infinite sequence: calculating a set of business days. Skip to the end for the cool stuff.

http://geekswithblogs.net/ryanohs/archive/2010/02/10/thinking-with-collections.aspx
Left by Ryan on Apr 14, 2010 5:36 AM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
Start with the sequence of all possible candidates {20..System.Int32.MaxValue}. Obviously must be 20 or bigger.
Now if divisible by 20, must also be divisible by 2, 4, 5, and 10.
So we only need to test for divisibility for numbers between 11 and 20. (10 will be covered by 20, 9 by 18, 8 by 16, .. etc.
So starting with the above sequence eliminate all numbers not divisible by 11. ie |> Seq.filter (fun x -> x % 11 = 0) and repeat for 12, 13, .. 20.
Then the first member of the sequence will be the result we want.
Thanks to lazy evaluation of sequences only those values of the sequence needed to be evaluated to produce a result are calculated.


let result =
{21..System.Int32.MaxValue}
|> Seq.filter (fun x -> x % 11 = 0)
|> Seq.filter (fun x -> x % 12 = 0)
|> Seq.filter (fun x -> x % 13 = 0)
|> Seq.filter (fun x -> x % 14 = 0)
|> Seq.filter (fun x -> x % 15 = 0)
|> Seq.filter (fun x -> x % 16 = 0)
|> Seq.filter (fun x -> x % 17 = 0)
|> Seq.filter (fun x -> x % 18 = 0)
|> Seq.filter (fun x -> x % 19 = 0)
|> Seq.filter (fun x -> x % 20 = 0)
|> Seq.head
Left by Peter Adams on Apr 15, 2010 1:51 AM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
Peter... once again I am reminded how much more I need to learn. That's a really simple way to solve it! And a totally different way of thinking of it than I would have taken. It's awesome, thanks!

How exactly does lazy evaluation work?
Left by Mark Pearl on Apr 15, 2010 6:23 AM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
When you write {1..System.Int32.MaxValue} you have declared a sequence of all integers from 1 to (a large number).
But nothing is actually calculated yet.
The sequence members are only calculated as they are needed in subsequent calculations.
To see how this works remove the final statement from the above function definition (ie take off the |> Seq.head line). Then highlight the code in the script file and hit alt enter.
You will see that it executes immediately, because we have not yet actually asked for a value, just defined a sequence of all multiples of 1..20.
Now enter result;; into F# interactive.
This asks for the first three values of the sequence to be printed, and at this point all of the calculations will be done. You will notice quite a delay compared with the first step.
Lazy means that we never calculate anything that someone hasn't actually asked to see.
Left by Peter Adams on Apr 15, 2010 7:47 AM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
Peter - how do you know if a function will be lazy or not. I was reading this blog post - http://weblogs.asp.net/podwysocki/archive/2008/03/21/adventures-in-f-f-101-part-6-lazy-evaluation.aspx - and they said you need to declare that something is lazy or not - but if I have a look at your code snippet I cannot see that declaration?

BTW - you expanded my mind today! thanks
Left by Mark Pearl on Apr 15, 2010 5:46 PM

# re: F# and the useful infinite Sequence (I think)
Requesting Gravatar...
In F# sequences are lazy by default. They work a bit like reading characters from a text file. Each time you want one, another one just pops up.
When you write an imperative program you are giving the computer step by step instructions, and 'driving' the machine, saying do this, then do that, now test that value, and branch to that instruction. An F# program, by contrast, is more like a specification of what you want.
In the above, we start off by saying that we want a sequence of all integers, then we say we want all of the members that aren't a multiple of 11 to be left out, then we say that all of those that are not multiples of 12 to be left out also, etc.
Up to this point the computer hasn't done a single thing to start to calculate the result.
It is not till the final step, when we ask for the head of the resulting sequence, that the computer gets up off its big fat butt, and actually starts to do something about finding an answer for us.
Maybe calling the computer lazy is being too kind.
Left by Peter Adams on Apr 16, 2010 11:16 PM

Your comment:
 (will show your gravatar)


Copyright © MarkPearl | Powered by: GeeksWithBlogs.net