为什么我感觉我的F#代码可能更简洁

Question

我是一名经验丰富的C#开发人员,他试图自学F#.我花了一天或三天的时间阅读F#wikibook试图了解语法和F#基础知识.

作为练习,我正在尝试通过Project Euler问题来更好地理解语法并使用该语言.

我刚刚解决了问题5.但是我不太高兴我必须跳过这个箍来获得代表我的解决方案的数据结构.我已经使用这个博文来获得解决问题的算法.

我想知道是否有人可以给我一些关于如何改进这些代码的指示？我的猜测是,F#值的固有不变性导致我必须执行大量步骤才能获得我想要的确切数据...

这是我的代码:

let main argv =
//calculates the prime factors of a number
let findPrimeFactors x =
    let primes = [|2I;3I;5I;7I;11I;13I;17I;19I|]
    let rec loop acc counter = function
        | x when x = 1I -> failwith "A PRIME IS BY DEFINITION GREATER THAN 1"
        | x when primes |> Array.contains x -> x :: acc
        | x when counter = primes.Length -> failwith "MY LIST OF KNOWN PRIMES IS NOT BIG ENOUGH"
        | x when x%primes.[counter]=0I-> loop (primes.[counter]::acc) (counter) (x/primes.[counter])
        | x -> loop acc (counter + 1) x

    let primeFactor = loop [] 0 x |> List.rev
    primeFactor

//calculates the prime factors for each of the numbers between 2 and n
//then, for each of the prime factorizations it tries to find the highest power for each occurring prime factor
let findPrimeFactorsPowers n =
    //builds a map of all the prime factor powers for all prime factorizations
    let rec addCounterFactorPowers factorPowers = function
        | counter when counter = n -> factorPowers
        | (counter : int) -> addCounterFactorPowers ((findPrimeFactors (counter|>bigint) |> List.countBy (fun x-> x)) @ factorPowers) (counter + 1)
    let allFactorPowers = addCounterFactorPowers [] 2
    //group all the powers per prime factor
    let groupedFactorPowers = allFactorPowers |> List.groupBy (fun (factor, power) -> factor)
    //get the highest power per prime factor
    let maxFactorPowers = groupedFactorPowers |> List.map (fun (key, powers) -> (key, powers |> List.map (fun (factor, power) -> power) |> List.max))

    //return the result
    maxFactorPowers        

let n = 20; 
let primeFactorSet = findPrimeFactorsPowers n
printfn "%A" primeFactorSet

let smallestNumberDivisableByAllNumbersBelown =  (primeFactorSet |> List.fold (fun state (factor, power) -> state * pown factor power) 1I)
printfn "Result %A" smallestNumberDivisableByAllNumbersBelown

System.Console.ReadKey(true)|>ignore
0 // return an integer exit code

Answer 1

您可以对代码应用许多直接简化,但我不认为这是最好的方法.

这是我在F#中解决这个问题的方法:

let rec tryDivide n m =
    if m = 1 then true
    else
        if n % m = 0 then tryDivide n (m-1)
        else false

let rec findIt i m =
    if tryDivide i m then i
    else findIt (i+1) m

findIt 1 20

它比你的慢一点,因为它不使用硬编码的素数,它们是在运行中计算的,但是我的计算机上仍需要不到2秒的时间才能得到正确的答案.

请注意,我没有使用任何类似列表的数据结构,也不需要在这个特定问题中依赖大整数.

UPDATE

这是基于Kvb提出的解决方案的更好方法:

let rec gcd x y = if y = 0 then abs x else gcd y (x % y)

let lcm a b = 
    match (a, b) with
    | (_, 0) | (0, _) ->  0
    | (x, y) -> abs ((x / (gcd x y)) * y)

Seq.fold lcm 1 {2..20}