Back to Questions
749
views3
comments
Any Comments on this LCD Implementation?
f#

I posted this in my weblog, but in an effort to get more feedback, I'm kind of reposting here. Sorry for the duplication.

In particular, one part of this code that pains me a little is having to use a dictionary to find the greatest powers of each prime factor in this function:

let leastCommonMultiple (n:seq<bigint>) =
let highestPowers = new Dictionary<bigint,int>()

n |> Seq.iter(fun x ->

primeFactors x

|> Seq.countBy (fun y -> y)

|> Seq.iter (fun (y, p) ->
if highestPowers.ContainsKey(y) then

if highestPowers.[y] < p then

highestPowers.[y] <- p
else

highestPowers.Add(y, p)))

highestPowers

|> Seq.map (fun x -> BigInt.pow x.Key (BigInt.of_int(x.Value)))

|> Seq.fold1 (fun x a -> BigInt.mul x a)

Is there a way to do this more functionally?

Also, questions lingering in the back of my mind:

  • Why doesn't bigint have more methods like sqrt? It seems like bigint and System.Decimal are the perfect numeric types for the types of problems F# is designed to work on, but they seem less well supported than float, double, and int.
  • I know I am just using pattern matching as a glorified if..then..else or switch (from c#) here. Are there ways I can improve this, or use other F# features to make this code better/more readable? Any other smells?
  • Any other suggestions for places to find really good numeric code in F#? I see a lot of examples, but some is very procedural. I really want to learn F# more than anything else.

<hints id="hah_hints"></hints>
Thanks in advance for any and all feedback!

.

Hi Chris,

I'm still refactoring of course, but here's my solution to Problem 5 on Project Euler:

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

 

#light

let inline (/:) d n = n % d = 0 // is multiple of
let inline pow x y = int ((float x) ** (float y))

let isPrime n = 
  let rec aux m n=
    m * m > n || not (m /: n) && aux (m + 1) n
  aux 2 n
  
let primesUpTo n = 
  seq { let x = ref 2
        while !x <= n do
          if isPrime !x then 
            yield !x
          do x := !x + 1 }

let getPrimeFactors n =
  let rec aux x acc =
    match Seq.tryfind (fun v -> v /: x) (primesUpTo x) with
    | Some(p) -> aux (x / p) (p::acc)
    | None -> acc
    
  aux n [] |> List.rev
  
let count n l = 
  n, l |> (List.filter ((=) n)) |> List.length

let distinct l =
  l |> Set.of_list |> Set.to_list

let countItems l =
  let rec aux l u acc =
    match u with
    | h::t -> aux l t ((count h l) :: acc)
    | [] -> acc
    
  aux l (distinct l) []
  
let lcm l =
  let addToMap t m =
    let n, c = t
    match Map.tryfind n m with
    | Some(v) when v < c -> Map.add n c m
    | None -> Map.add n c m
    | _ -> m

  let rec outerLoop l m =
    match l with
    | h::t -> outerLoop t (innerLoop h m)
    | [] -> m
  and innerLoop l m =
    match l with
    | h::t -> innerLoop t (addToMap h m)
    | [] -> m

  let factors = l |> List.map getPrimeFactors |> List.map countItems
  
  outerLoop factors Map.empty |> Map.to_list |> List.fold_left (fun r (n, c) -> r * (pow n c)) 1

<i>very<i> fun to write! :-)

By on 3/4/2008 7:39 PM ()

Thanks Dustin! Your "Why I Love F#" series is aweseome! It's great for when I want to explain something I like about F# to someone succinctly and in a way that's easy to understand.

Things I learned from your sample:

* I haven't used Maps at all in F#! I need to get familliar with them.
* I like this use of operators (/:) Need to learn the limits of this.
* This code:

1
2

let count n l = 
  n, l |> (List.filter ((=) n)) |> List.length

I need to get familliar with this - so, count yields a tuple of n and the number of elements = n in l?

I like the way F# is so "wrist friendly" but sometimes this throws me off.<hints id="hah_hints"></hints>

By on 3/5/2008 4:46 AM ()

* This code:

1
2

let count n l = 
  n, l |> (List.filter ((=) n)) |> List.length

I need to get familliar with this - so, count yields a tuple of n and the number of elements = n in l?
<HINTS id=hah_hints></HINTS>

That's right. TBH, I may have been a bit <i>too<i> clever with this method. I think the readability suffers a bit, and the function name isn't great. Maybe something like this? <code lang=fsharp> let inline equals x y = x = y let count x lst = lst |> List.filter (equals x) |> List.length let pairWithCount x lst = x, (count x lst) </code>

By on 3/5/2008 11:08 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