SublimeTextのfuzzy search algorithmをHaskellで書いてみた。 参考：http://www.quora.com/Algorithms/How-is-the-fuzzy-search-algorithm-in-Sublime-Text-designed

FuzzyMatch.hs

module FuzzyMatch where

import           Data.Char (toLower)

-- $setup
-- import Data.List (sort)
-- >>> let searchSet = ["Strings to search, one per line", "diff_match_patch.js", "diff_match_patch_uncompressed.js", "diff_match_patch_test.js"]

-- |
-- >>> Data.List.sort $ fuzzyMatch searchSet "mas"
-- ["diff_match_patch.js","diff_match_patch_test.js","diff_match_patch_uncompressed.js"]
--
-- >>> Data.List.sort $ fuzzyMatch searchSet "mau"
-- ["diff_match_patch_uncompressed.js"]
fuzzyMatch :: [String] -> String -> [String]
fuzzyMatch ws query = filter (isMatch (map toLower query)) ws
  where
    -- |
    -- >>> isMatch "ms" "match"
    -- False
    --
    -- >>> isMatch "ms" "mouse"
    -- True
    isMatch :: String -> String -> Bool
    isMatch [] _ = True
    isMatch _ [] = False
    isMatch query'@(q:qs) (x:xs)
        | q == toLower x = isMatch qs xs
        | otherwise      = isMatch query' xs