fastedit (empty) → 0.1.0.0

raw patch · 5 files changed

+103/−0 lines, 5 filesdep +QuickCheckdep +basedep +base-preludesetup-changed

Dependencies added: QuickCheck, base, base-prelude, bytestring, containers, edit-distance, fastedit, file-embed, hashable, hspec, safe, unordered-containers

Files

• LICENSE +0/−0
• Setup.hs +2/−0
• fastedit.cabal +48/−0
• src/Text/FastEdit.hs +51/−0
• test/Spec.hs +2/−0

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,48 @@+-- Initial fastedit.cabal generated by cabal init.  For further+-- documentation, see http://haskell.org/cabal/users-guide/++name:                fastedit+version:             0.1.0.0+synopsis:            find nearest neighbours by edit-distance+description:         Use faroo's deletion algorithm to generate possible+                     autocorrections efficiently+license:             MIT+license-file:        LICENSE+author:              Mark Wotton+maintainer:          mwotton@gmail.com+build-type:          Simple+cabal-version:       >=1.10+category:            Text+source-repository head+  type: git+  location: http://github.com/mwotton/fastedit.git++library+  exposed-modules:     Text.FastEdit+  build-depends:       base >=4.7 && <4.8,+                       base-prelude,+                       unordered-containers,+                       containers,+                       safe,+                       bytestring,+                       hashable+  ghc-prof-options: -fprof-auto+  hs-source-dirs:      src+  default-language:    Haskell2010+++test-suite tests+  default-language:    Haskell2010+  hs-source-dirs: test+  main-is:       Spec.hs+  type: exitcode-stdio-1.0+  ghc-options: -Wall -threaded -rtsopts+  ghc-prof-options: -fprof-auto+  build-depends: base+               , fastedit+               , base-prelude+               , hspec+               , edit-distance+               , QuickCheck+               , file-embed+               , bytestring

@@ -0,0 +1,51 @@+{-# LANGUAGE TupleSections #-}++module Text.FastEdit where++import           BasePrelude+import qualified Data.ByteString.Lazy.Char8 as BL+import           Data.Hashable              (Hashable)+import qualified Data.HashMap.Strict        as HM+import qualified Data.HashSet               as HS+import qualified Data.Sequence              as Seq+import           Prelude                    ()+import           Safe                       (atMay)++cantorise :: (a -> b -> [c]) -> [a] -> [b] -> [c]+cantorise f as bs = concat $ mapMaybe+                    (\(ai,bi) -> do+                        a <- atMay as ai+                        b <- atMay bs bi+                        return $ f a b) $ take (length as * length bs) antiDiagonals++antiDiagonals :: [(Int, Int)]+antiDiagonals = concatMap anti [0..]+  where anti n = zip [0..n] (reverse [0..n])++buildDict :: Int -> [String] -> String -> [String]+buildDict n dictWords = \s -> nub $ cantorise searchDict (deletions s) dicts+  where+    searchDict candidates dict = concat $ mapMaybe (`HM.lookup` dict) candidates+    dicts = map (fmap HS.toList . builder) $ transpose $ map (take n . tagged) dictWords+    builder = HM.fromListWith HS.union . concatMap (\(a,as) -> map (,HS.singleton a) as)+    tagged s = map (s,) (deletions s)++deletions :: String -> [[BL.ByteString]]+deletions s = map (ordNub . deleteN s) [0..(length s)]++deleteN :: String -> Int -> [BL.ByteString]+deleteN s n = map BL.pack $ toList $ go s n+  where+    go :: String -> Int -> Seq.Seq String+    go s 0 = Seq.singleton s+    go (x:xs) n = go xs (n-1) <> fmap (x:) (go xs n)+    go [] _ = Seq.empty+++-- ordNub :: (Hashable t, Eq t) => [t] -> [t]+ordNub :: (Hashable t, Eq t) => [t] -> [t]+ordNub = go HS.empty+  where+    go _ [] = []+    go s (x:xs) = if x `HS.member` s then go s xs+                  else x : go (HS.insert x s) xs

@@ -0,0 +1,2 @@+-- file test/Spec.hs+{-# OPTIONS_GHC -F -pgmF hspec-discover #-}