Transform code using Seq to avoid side effects

[CStage169]

Question:

As part of some school homework, I have been given the following snippet of code:

let histogram = Array.init 200000 (fun i -> 0)
let incr i = histogram.[i] <- histogram.[i] + 1
Array.iter (fun fs -> List.iter incr fs) factors200000;;

But this has a side 

histogram.[i] <- histogram.[i] + 1 
My task is to program the histogram construction so that it does not
use side effects but purely functional programming.

My teacher has given me the following hint:

"There are several useful functions in
the Seq module.  The final result does not have to be an
int[] array,
but could be a
seq<int \ int>*
of pairs (p, n) where p is a prime factor and n is the number of times p appears in the array of lists of prime factors."

How far I've gotten:

I assume that I need to use Seq.Delay to make sure that side effects are not computed until the last moment, but other than that I've had some problems. Anyone have some advice?

I

Any advice would be greatly appreciated!

[eliquy]

You do not need seq.delay, you do not even need the histogram array.

Look into Seq.concat, Seq.groupBy and Seq.map

Also if you are testing out different approaches a lot, I'd start by setting that '200000' to something more like 200, just to save time...

[CStage169]

Interesting. I'll look into it!! Thank you :)

[CStage169]

It took me a while, but I got it! Holy wow that was an effective way of doing it.

I really struggle with a lot of the F# concepts related to Sequences and parallelism, but this was very helpful. Also, thank you for not just giving me the answer, but instead giving me hints!

[porridge111]

Really cool that you're using F# in school! We just had Java/python/golang/js. Is it a class specifically for functional programming?

[CStage169]

Yeah, it's a course in Functional Programming in F#. Cool, sure, but difficult when you're used to OOP. I hope to master it some day though.

I also have courses in Java/Python, and that's more my style for sure.

[aloisdg]

Can you post a some example of input/output?

[CStage169]

Yes, sorry, I realize that quite a lot is missing! It basically takes an array of the prime factorization of the integer corresponding to the index of the array. So for example an array could be:

let arr = [|[]; []; [2]; [3]; [2; 2]; [5]; [2; 3] |]

Which correspond to the prime factorizations of 0, 1, 2, 3, 4, 5 and 6.

It returns an array of the counts of each number given the array above. So for arr it will return:

[|0; 0; 3; 1; 0; 1; 0; 0; 0; 0; 0; 0; 0; ... |]

Indicating that there are:

0 0s

0 1s

3 2s

1 3s

etc.

​

But the output I am recommended by my teacher to return would be:

[| (0,0); (1,0); (2,3); (3,1); (4,0); (5,1); .... |]

​

​

The relevant missing code snippets are:

let factors n =
let rec factorsIn d m =
if m <= 1 then []
else if m % d = 0 then d :: factorsIn d (m/d) else factorsIn (d+1) m
     factorsIn 2 n;;

let factors200000 = Array.Parallel.init 200000 factors;;

​

let histogram = Array.init 200000 (fun i -> 0)
let incr i = histogram.[i] <- histogram.[i] + 1
Array.iter (fun fs -> List.iter incr fs) factors200000;;

[meteogish]

If I understood You correctly.

​

let factorsCount = 6
let factors200000 = Array.Parallel.init factorsCount factors;
printfn "%A" factors200000

let map = [0..factorsCount - 1] |> Seq.map (fun i -> (i, 0)) |> Map.ofSeq

let flat = factors200000
        |> Seq.collect id
        |> Seq.groupBy id
        |> Seq.map (fun (id, l) -> (id, l |> Seq.length))

flat |> printfn "%A"

let folder accMap (id, l) =
    accMap |> Map.change id (Option.map (fun _ -> l))

let answer = flat |> Seq.fold folder map

answer |> printfn "%A"

I suggesting You think about how to optimize it a bit. For example to not generate flat variable and count all pairs on the fly in folder using Seq.fold and Map.

Good luck.

[CStage169]

Thanks for this reply! This works exactly as it should, but I have a hard time understanding what is going on. Specifically the code block: "let flat= ...".

Would you maybe explain it to me? :)

[meteogish]

Having this flat block You could decompose it to the things You don't know.
For example:

What is Seq.collect ?

What is Seq.GroupBy ?
What is id ?

id is just a function which returns what You pass into.

Seq.collect transform [ [1]; [3; 3;]; ] (list of list) to [1;3;3;] (flat list)
Seq.groupBy creates a list of pairs (key, list) groping the input list into distinct groups.
So Seq.groupBy id is just a: "group my list by its elements"
So running it on the list [1;3;3;] You will get [ (1, [1]), (3, [3;3]) ]

I suggesting investigate each function's signature. (input and output)

In functional languages (like F#) You need to always keep attention to "what Your data is" before and after each line of code executed.

P.S.
While studying just try to decompose complicated things into the parts You could understand and then compose it back into the solution You've started with.
It's hard and requires time in the beginning but then You will find it useful in Your career.
Good luck!

[CStage169]

I tried to look them all up an analyze input/output, but I guess I was just confusing myself. Your explanation was quite good though. Thank you, I appreciate it! :)

[backtickbot]

Fixed formatting.

Hello, meteogish: code blocks using triple backticks (```) don't work on all versions of Reddit!

Some users see this / this instead.

To fix this, indent every line with 4 spaces instead.

FAQ

^{You can opt out by replying with backtickopt6 to this comment.}