Meeting this coming Tuesday, October 25

[Mark Wutka]

Hi Everyone!

It sure seems like time is flying, we're already coming up on our next meeting this coming tuesday, the 25th. Does anyone have anything they would like to present?

[Patrick Carver]

I just now pinged Bryan for a Zoom link for tonight's meetup

[Patrick Carver]

Zoom link for tonight's meeting: https://us02web.zoom.us/j/84221468136?pwd=MXZBQURPTHRZMzh2OWwzT0M2YnVWZz09

[Jason Orendorff]

-- A Haskell program for finding all needles in a haystack, as long as the needles and the haystack
-- are both strings.

import System.Environment(getArgs)
import Data.List(tails, isPrefixOf, sortOn)

-- lame O(ST) algorithm:
-- findAll t s = map fst $ filter (\(i, t') -> s `isPrefixOf` t') (zip [0..] (tails t))

-- still O(ST), if not worse, but using a fancy **suffix array**!!!!
findAll t = \s -> filter (\i -> s `isPrefixOf` drop i t) suffixArray
  where suffixArray = map fst $ sortOn snd $ (zip [0..] (tails t))

-- The idea is, you would use arrays instead of lists, and then the suffix array
-- can be used to make each search O(S log T) or even, if you think a little
-- harder about it, O(S + log T).

main = do
  [haystack, needle] <- getArgs
  putStrLn $ show $ findAll haystack needle

--
You received this message because you are subscribed to the Google Groups "Nashville Functional Programmers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to nashfp+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/nashfp/66d1181b-548f-4b3a-bbf6-5d67fa6b9fa4n%40googlegroups.com.