5
\$\begingroup\$

I've been learning F# for a month or so and I'm wondering how good my "functional" aspect of coding is. When I first started, I did this using an iterative approach with a lot of <- and mutables etc. I tried to rewrite it as functional as possible. Any critique is appreciated.

This code prints out all anagrams in the english dictionary read from a "word.txt" file, the LONGEST anagram, and the anagram with the MOST permutations.

open System

let sortStringAsKey (listOfWords : string array) = 
    let getKey (str : string) = 
        str.ToCharArray() 
        |> Array.sort 
        |> String

    listOfWords 
    |> Array.groupBy getKey 
    |> Array.filter (fun (sortedWord, originalWord) -> originalWord.Length > 1)


[<EntryPoint>]
let main argv = 
    let filename = "words.txt"
    let listOfWords = System.IO.File.ReadAllLines(filename)
    let listOfAnagrams = sortStringAsKey listOfWords

    // Prints every single anagram combination
    listOfAnagrams |> Array.iter  (fun (_ , anagramList) ->  anagramList |> Array.iter (fun str -> printfn "%s" str); printfn "")

    // Gets the LONGEST anagram
    let longestAnagrams = listOfAnagrams 
                        |> Array.filter (fun (sortedWord, _) -> sortedWord.Length >= (listOfAnagrams 
                                                                                        |> Array.maxBy (fun (sortedWord, _)-> sortedWord.Length) 
                                                                                        |> fst 
                                                                                        |> String.length))

    // Gets the set that has the MOST anagrams
    let mostAnagrams = listOfAnagrams
                        |> Array.filter (fun (_, originalWords) -> originalWords.Length >= (listOfAnagrams 
                                                                                            |> Array.maxBy (fun (_, originalWords) -> originalWords.Length) 
                                                                                            |> snd 
                                                                                            |> Array.length))

    // Prints the longest and most anagrams
    longestAnagrams |> Array.iter  (fun (_ , anagramList) ->  anagramList |> Array.iter (fun str -> printfn "%s" str); printfn "")
    mostAnagrams |> Array.iter  (fun (_ , anagramList) ->  anagramList |> Array.iter (fun str -> printfn "%s" str); printfn "")


    0 // return an integer exit code
\$\endgroup\$
  • \$\begingroup\$ At a glance, it looks like a good start. There are few ways you could trim the code a bit. Could you share a sample dictionary file you use for testing? That way, I'd be better able to verify if any potential suggestions I might have are feasible. If you have a test suite, it'd be even better. \$\endgroup\$ – Mark Seemann Mar 20 '16 at 9:07
  • \$\begingroup\$ @MarkSeemann Of course, I simply went to this website mieliestronk.com/corncob_lowercase.txt and copy pasted it in a text file called words.txt. I appreciate the help :) I'm also not that familiar at making test suites so I'd appreciate any sources on how to make them. \$\endgroup\$ – Luke Xu Mar 20 '16 at 15:23
5
\$\begingroup\$

This looks like a good start, so the following is by no means a criticism, but there are various refactorings you can perform to make the code smaller, and more generic.

As a general comment, I'd advise against naming arrays listOfWhatever, since list is a concrete data type in F#, separate from arrays. I've renamed listOfWords to words, listOfAnagrams to anagrams, and so on.

Finding the anagrams

The first sortStringAsKey function doesn't need type annotations if you refactor it a bit:

// seq<'a> -> seq<string * seq<'a>> when 'a :> seq<char>
let sortStringAsKey words = 
    words
    |> Seq.groupBy (Seq.sort >> Seq.toArray >> String)
    |> Seq.filter (fun (_, originalWords) -> Seq.length originalWords > 1)

You'll notice that I inlined the getKey function, but perhaps that's taking it too far. If you think that having a named local function makes the code more readable, I wouldn't disagree.

I've also changed from working explicitly with arrays, to using the Seq module. This makes the function more generic, but it can still handle arrays.

You could even perform an eta reduction on the function, in order to make it even shorter, but I'm not sure it becomes more readable by it:

let sortStringAsKey =
    Seq.groupBy (Seq.sort >> Seq.toArray >> String)
    >> Seq.filter (fun (_, originalWords) -> Seq.length originalWords > 1)

Just for the fun, you can make it even more cryptic:

let sortStringAsKey =
    Seq.groupBy (Seq.sort >> Seq.toArray >> String)
    >> Seq.filter (snd >> Seq.length >> ((<) 1))

Personally, I don't even find that readable myself; I'd prefer the first, most verbose option.

Printing the anagrams

Since there's at least three places where the code prints out the anagrams, it's more reasonable to turn that into a function:

// seq<string> -> unit
let prints a =
    a |> Seq.iter (printfn "%s")
    printfn ""

Once again, you'll notice that I chose to use Seq.iter instead of Array.iter. It'll still be able to handle arrays, but there's no reason to constrain the input if it isn't necessary.

Loading anagrams

Loading the anagrams from file can be simplified a bit as well, since you don't need the intermediate listOfWords value:

// In main function:
let filename = "../../words.txt"
let anagrams = System.IO.File.ReadAllLines(filename) |> sortStringAsKey

Because of the more generic version of sortStringAsKey, the type of anagrams is seq<string * seq<string>>.

Printing all the anagrams

With the prints function, you can easily print all the anagrams

anagrams |> Seq.map snd |> Seq.iter prints

Instead of performing work inside on of Seq.iter (which is possible), I often prefer to perform transformations etcetera first, because I can easily test such pure functions. Once you have data in the appropriate shape, you can always use Seq.iter to e.g. print it.

Finding the longest anagrams

The proposed solution suffers from calling Array.maxBy for every element, so it'd be quite inefficient.

You can make it more efficient by only doing it once:

let longestAnagrams = 
    let longest = anagrams |> Seq.map (fst >> String.length) |> Seq.max
    anagrams |> Seq.filter (fst >> String.length >> ((=) longest))

This still requires two traversals of the array, so isn't as efficient as it could be, but is probably (but measure instead of assume, when it comes to performance) more efficient than doing Array.maxBy for every entry.

See below for an optional refactoring.

Finding the words with most anagrams

Likewise, you can find the largest collections of anagrams:

let mostAnagrams =
    let most = anagrams |> Seq.map (snd >> Seq.length) |> Seq.max
    anagrams |> Seq.filter (snd >> Seq.length >> ((=) most))

Notice how this is similar to longestAnagrams.

Printing

Both longestAnagrams and mostAnagrams can be printed using the prints function:

longestAnagrams |> Seq.map snd |> Seq.iter prints
mostAnagrams |> Seq.map snd |> Seq.iter prints

Alternative max and filter operation

The problem with even the refactored version of longestAnagrams is that it requires two traversals of the sequence in order to compute the results.

Once you realise that the operation is essentially a fold, you may want to optimise it to a single traversal:

let longestAnagrams = 
    let folder l (k, v) =
        let xl = Seq.length k
        match xl, l with
        | _, []                                  -> [k, v]
        | x, (hk,  _)::_ when xl > Seq.length hk -> [k, v]
        | x, (hk, hv)::t when xl = Seq.length hk -> (k, v)::(hk, hv)::t
        | _                                      -> l
    anagrams |> Seq.fold folder []

As you can tell, it's more code (so more complicated), but at least in theory more efficient, as it only uses a single traversal. It does, however, potentially causes more memory allocations, so as always when performance is involved: measure.

On my machine, though, it seems to be more than twice as fast...

You can refactor the computation of mostAnagrams in the same way, but I will leave that as an exercise ;)

\$\endgroup\$
  • \$\begingroup\$ Wow!!! This is amazing! Thank you :D My company uses hungarian notation for coding and it's hard to forget the bad habbit :p You're absolutely right though. All of this is very helpful! \$\endgroup\$ – Luke Xu Mar 20 '16 at 21:48
  • 1
    \$\begingroup\$ As you alluded to the similarity, you can generify longestAnagrams into e.g. Seq.multiMaxBy f xs. Then let longestAnagrams = anagrams |> Seq.multiMaxBy (fst >> String.length), and let mostAnagrams = anagrams |> Seq.multiMaxBy (snd >> Seq.length) \$\endgroup\$ – Dax Fohl Mar 21 '16 at 2:11
  • 1
    \$\begingroup\$ Also when defining anagrams, make sure to convert to list or array; seq is lazy and so leaving anagrams as a seq causes sortStringAsKey to be executed every time anagrams is iterated. Similarly it'd be more efficient if the grouped originalWords was a list/array so that Count is cached, but measurement shows this is a smaller problem. \$\endgroup\$ – Dax Fohl Mar 21 '16 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.