Anonymous user
Hash join: Difference between revisions
Added Haskell
No edit summary |
(Added Haskell) |
||
Line 22:
Implement the Hash Join algorithm in your programming language (optionally providing a test case as well).
=={{header|Haskell}}==
The ST monad allows us to utilise mutable memory behind a referentially transparent interface, with the s type variable prevent the mutable state being modifying by more than one thread.
<lang Haskell>import qualified Data.HashTable.ST.Basic as H
import Data.Hashable
import Control.Monad.ST
import Control.Monad
import Data.STRef
hashJoin :: (Eq k, Hashable k) =>
[t] -> (t -> k) -> [a] -> (a -> k) -> [(t, a)]
hashJoin xs fx ys fy = runST $ do
l <- newSTRef []
ht <- H.new
forM_ ys $ \y -> H.insert ht (fy y) =<<
(H.lookup ht (fy y) >>= \case
Nothing -> return [y]
Just v -> return (y:v))
forM_ xs $ \x -> do
H.lookup ht (fx x) >>= \case
Nothing -> return ()
Just v -> modifySTRef' l ((map (x,) v) ++)
readSTRef l
test = mapM_ print $ hashJoin
[(1, "Jonah"), (2, "Alan"), (3, "Glory")] snd
[("Jonah", "Whales"), ("Jonah", "Spiders"),
("Alan", "Ghosts"), ("Alan", "Zombies"), ("Glory", "Buffy")] fst
</lang>
<pre>λ> test
((3,"Glory"),("Glory","Buffy"))
((2,"Alan"),("Alan","Zombies"))
((2,"Alan"),("Alan","Ghosts"))
((1,"Jonah"),("Jonah","Spiders"))
((1,"Jonah"),("Jonah","Whales"))
</pre>
| |||