How to Make a Thing in Haskell, Part 7: Scoring and Sorting

I’ve successfully translated Gary Bernhardt’s scoring function into Haskell now! It uses matchLength from my previous post and scores based on the shortest match it can find and the relative lengths of the query and choice string:

score :: String -> String -> Rational
score ""    _      = 1
score _     ""     = 0
score query choice =
    let match = shortestMatchLength (lower query) (lower choice)
    in case match of
        Nothing -> 0
        Just x  ->
            genericLength query / fromIntegral x / genericLength choice

shortestMatchLength :: Eq a => [a] -> [a] -> Maybe Integer
shortestMatchLength []          _      = Just 0
shortestMatchLength query@(q:\_) choice =
    let matchQuery = matchLength query
        candidates = suffixesStartingWith q choice
        lengths = mapMaybe matchQuery candidates
    in case lengths of
        [] -> Nothing
        xs -> Just (minimum xs)

shortestMatchLength is another function that returns an option type, using Nothing to indicate the absence of a match. score, like the module name says, is where the magic happens. A couple cool things came up as I was writing these functions:

So now, I’m done reimplmenting selecta’s algorithmic core in Haskell. It seems to work pretty well. In ghci:

λ import Skellect.Score
λ import Data.List (sortBy)
λ import Data.Ord (comparing)
λ let choices = ["lots-of-files","business-papers","lol-worthy","a little odd"]
λ let choiceScores = zip choices $ map (score "lol") choices
λ choiceScores
[("lots-of-files",3 % 143),("business-papers",0 % 1),("lol-worthy",1 % 10),("a little odd",0 % 1)]
λ let positiveScores = filter ((>0) . snd) choiceScores
λ positiveScores
[("lots-of-files",3 % 143),("lol-worthy",1 % 10)]
λ let sortedDescending = reverse . sortBy (comparing snd) $ positiveScores
λ sortedDescending
[("lol-worthy",1 % 10),("lots-of-files",3 % 143)]
λ map fst sortedDescending
["lol-worthy","lots-of-files"]

A quick translation of the functions used here that you might not have seen if you don’t write Haskell:

  • zip takes 2 lists, [1a,1b,1c] and [2a,2b,2c], and returns them “zipped” into a list of tuples: [(1a,2a),(1b,2b),(1c,2c)]
  • fst takes a 2-tuple and returns the first element; similarly, snd returns the second.
  • sortBy takes a comparison function and a list and returns the elements of the list sorted by the function. comparing takes a function that returns something orderable and returns a function that sortBy can use to sort with.

So, when the time comes to actually use score to sort stuff, that can be our pipeline:

λ let sortedPositiveScores q cs = map fst . reverse . sortBy (comparing snd) . filter ((>0) . snd) $ zip cs $ map (score q) cs
λ sortedPositiveScores "lol" ["lots-of-files","business-papers","lol-worthy","a little odd"]
["lol-worthy","lots-of-files"]

Almost completely unreadable, at least to my eyes! But: it’s neat to look at the way these functions all compose into a single unit that does exactly what I want.

  1. There’s a Safe package that implements a minimumMay function, but I want to avoid dependencies and stick to the standard library as much as possible.