Hash join: Difference between revisions
Content added Content deleted
No edit summary |
(Added Haskell) |
||
Line 22: | Line 22: | ||
Implement the Hash Join algorithm in your programming language (optionally providing a test case as well). |
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> |