Can I Use A Fold (or Some Other Kind Of Reduce) For This Code?

Onorio_Catenacci_2820 0
Viewed 68

I'm trying to rekindle my knowledge of F#. For practice I built an implementation of calculating the FNV1a32 hash of a string in F#.

This is the code I came up with:

let XorWithHash b hash =
   hash ^^^ b

let MultiplyByPrimeFactor hash =
   let Prime = 16777619un   
   hash * Prime

let GetNthByteOfString (s:string) n =
   if (n < Encoding.UTF8.GetByteCount(s)) then Some(unativeint (Encoding.UTF8.GetBytes(s).[n])) else None


let GetFNV1a32 s =
   let rec transformString s n (acc:unativeint)=
      let b = GetNthByteOfString s n 
      match b with
      | Some b -> 
         XorWithHash b acc 
         |> MultiplyByPrimeFactor
         |> transformString s (n+1)
      | None -> acc

   let OffsetBasis = 2166136261un
   transformString s 0 OffsetBasis

let Main =
   let answer = GetFNV1a32 "Test String"
   answer

And it works correctly and I'm fine with that. My question is this: I think I could simplify the implementation of transformString if I could use a fold or some other sort of reduce but I can't quite seem to figure it out. Can anyone help me out with an implementation of transformString that uses a fold or reduce of some sort? Or is this as good as I'm likely to get?

hash f#
1 Answers

You certainly can, and this is what that looks like:

let GetFNV1a32 (s: string) =
    let offsetBasis = 2166136261un
    // We only have to get the bytes once; now we have an entire array that we can perform monadic operations on
    Encoding.UTF8.GetBytes s
    // Array.fold's signature is ('State -> 't -> 'State) -> 'State -> 't[] -> 'State
    // So here 'State is unativeint, and 't is byte, which is the current item of the byte[]. We can just transform it in one go to our output value, which becomes the value of acc the next time around.
    |> Array.fold (fun acc byt -> MultiplyByPrimeFactor (XorWithHash (unativeint byt) acc))
        offsetBasis   // initial value

Here's a quick test to show that it works, given GetFNV1a32_old to be the OP:

let xs =
    [for str in ["TestString"; "Test String"; "foo BAR"; "BÄz qúåx"] do
        let old, neww = GetFNV1a32_old str, GetFNV1a32 str
        yield old, neww, (sprintf "does old = neww? %b" (old = neww))]

Which results in:

val xs : (unativeint * unativeint * string) list =
   [(17683775798505137816un, 17683775798505137816un, "is old = neww? true");
    (3444292159790811978un, 3444292159790811978un, "is old = neww? true");
    (17137498406203898314un, 17137498406203898314un, "is old = neww? true");
    (13890330577974722754un, 13890330577974722754un, "is old = neww? true")]
user_12319250
Related