module Heidi.Data.Frame.Algorithms.GenericTrie (
unionColsWith
, spreadWith, gatherWith
, groupBy, innerJoin, leftOuterJoin
) where
import Data.Maybe (fromMaybe)
import qualified Data.Foldable as F (foldMap, foldl', foldlM)
import qualified Data.Map as M
import qualified Data.Set as S (Set, fromList)
import qualified Data.GenericTrie as GT
import Core.Data.Frame.List (Frame, frameFromList, zipWith)
import qualified Heidi.Data.Row.GenericTrie as GTR
import Prelude hiding (filter, zipWith, lookup, foldl, foldr, scanl, scanr, head, take, drop)
unionColsWith :: (Eq k, GT.TrieKey k) =>
(v -> v -> v)
-> Frame (GTR.Row k v)
-> Frame (GTR.Row k v)
-> Frame (GTR.Row k v)
unionColsWith :: (v -> v -> v)
-> Frame (Row k v) -> Frame (Row k v) -> Frame (Row k v)
unionColsWith v -> v -> v
f = (Row k v -> Row k v -> Row k v)
-> Frame (Row k v) -> Frame (Row k v) -> Frame (Row k v)
forall a b c. (a -> b -> c) -> Frame a -> Frame b -> Frame c
zipWith ((v -> v -> v) -> Row k v -> Row k v -> Row k v
forall k v.
TrieKey k =>
(v -> v -> v) -> Row k v -> Row k v -> Row k v
GTR.unionWith v -> v -> v
f)
gatherWith :: (Foldable t, Ord k, GT.TrieKey k) =>
(k -> v)
-> S.Set k
-> k
-> k
-> t (GTR.Row k v)
-> Frame (GTR.Row k v)
gatherWith :: (k -> v) -> Set k -> k -> k -> t (Row k v) -> Frame (Row k v)
gatherWith k -> v
fk Set k
ks k
kKey k
kValue = [Row k v] -> Frame (Row k v)
forall row. [row] -> Frame row
frameFromList ([Row k v] -> Frame (Row k v))
-> (t (Row k v) -> [Row k v]) -> t (Row k v) -> Frame (Row k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Row k v -> [Row k v]) -> t (Row k v) -> [Row k v]
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
F.foldMap Row k v -> [Row k v]
f where
f :: Row k v -> [Row k v]
f Row k v
row = (k -> v) -> Set k -> Row k v -> k -> k -> [Row k v]
forall k v.
(Ord k, TrieKey k) =>
(k -> v) -> Set k -> Row k v -> k -> k -> [Row k v]
gather1 k -> v
fk Set k
ks Row k v
row k
kKey k
kValue
gather1 :: (Ord k, GT.TrieKey k) =>
(k -> v)
-> S.Set k
-> GTR.Row k v
-> k
-> k
-> [GTR.Row k v]
gather1 :: (k -> v) -> Set k -> Row k v -> k -> k -> [Row k v]
gather1 k -> v
fk Set k
ks Row k v
row k
kKey k
kValue = [Row k v] -> Maybe [Row k v] -> [Row k v]
forall a. a -> Maybe a -> a
fromMaybe [] (Maybe [Row k v] -> [Row k v]) -> Maybe [Row k v] -> [Row k v]
forall a b. (a -> b) -> a -> b
$ ([Row k v] -> k -> Maybe [Row k v])
-> [Row k v] -> Set k -> Maybe [Row k v]
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
F.foldlM [Row k v] -> k -> Maybe [Row k v]
insf [] Set k
ks where
rowBase :: Row k v
rowBase = Set k -> Row k v -> Row k v
forall k (t :: * -> *) v.
(TrieKey k, Foldable t) =>
t k -> Row k v -> Row k v
GTR.deleteMany Set k
ks Row k v
row
lookupInsert :: k -> Maybe (Row k v)
lookupInsert k
k = do
v
x <- k -> Row k v -> Maybe v
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k Row k v
row
let
r' :: Row k v
r' = k -> v -> Row k v -> Row k v
forall k v. TrieKey k => k -> v -> Row k v -> Row k v
GTR.insert k
kKey (k -> v
fk k
k) Row k v
rowBase
r'' :: Row k v
r'' = k -> v -> Row k v -> Row k v
forall k v. TrieKey k => k -> v -> Row k v -> Row k v
GTR.insert k
kValue v
x Row k v
r'
Row k v -> Maybe (Row k v)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Row k v
r''
insf :: [Row k v] -> k -> Maybe [Row k v]
insf [Row k v]
acc k
k = do
Row k v
r' <- k -> Maybe (Row k v)
lookupInsert k
k
[Row k v] -> Maybe [Row k v]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([Row k v] -> Maybe [Row k v]) -> [Row k v] -> Maybe [Row k v]
forall a b. (a -> b) -> a -> b
$ Row k v
r' Row k v -> [Row k v] -> [Row k v]
forall a. a -> [a] -> [a]
: [Row k v]
acc
{-# inline gather1 #-}
spreadWith :: (GT.TrieKey k, Foldable t, Ord k, Ord v) =>
(v -> k)
-> k
-> k
-> t (GTR.Row k v)
-> Frame (GTR.Row k v)
spreadWith :: (v -> k) -> k -> k -> t (Row k v) -> Frame (Row k v)
spreadWith v -> k
fk k
k1 k
k2 = [Row k v] -> Frame (Row k v)
forall row. [row] -> Frame row
frameFromList ([Row k v] -> Frame (Row k v))
-> (t (Row k v) -> [Row k v]) -> t (Row k v) -> Frame (Row k v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Row k v, Row k v) -> Row k v)
-> [(Row k v, Row k v)] -> [Row k v]
forall a b. (a -> b) -> [a] -> [b]
map (Row k v, Row k v) -> Row k v
forall k v. TrieKey k => (Row k v, Row k v) -> Row k v
funion ([(Row k v, Row k v)] -> [Row k v])
-> (t (Row k v) -> [(Row k v, Row k v)])
-> t (Row k v)
-> [Row k v]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map (Row k v) (Row k v) -> [(Row k v, Row k v)]
forall k a. Map k a -> [(k, a)]
M.toList (Map (Row k v) (Row k v) -> [(Row k v, Row k v)])
-> (t (Row k v) -> Map (Row k v) (Row k v))
-> t (Row k v)
-> [(Row k v, Row k v)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Map (Row k v) (Row k v) -> Row k v -> Map (Row k v) (Row k v))
-> Map (Row k v) (Row k v)
-> t (Row k v)
-> Map (Row k v) (Row k v)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' ((v -> k)
-> k
-> k
-> Map (Row k v) (Row k v)
-> Row k v
-> Map (Row k v) (Row k v)
forall k v.
(Ord k, Ord v, TrieKey k, Eq k) =>
(v -> k)
-> k
-> k
-> Map (Row k v) (Row k v)
-> Row k v
-> Map (Row k v) (Row k v)
spread1 v -> k
fk k
k1 k
k2) Map (Row k v) (Row k v)
forall k a. Map k a
M.empty
where
funion :: (Row k v, Row k v) -> Row k v
funion (Row k v
km, Row k v
vm) = Row k v -> Row k v -> Row k v
forall k v. TrieKey k => Row k v -> Row k v -> Row k v
GTR.union Row k v
km Row k v
vm
spread1 :: (Ord k, Ord v, GT.TrieKey k, Eq k) =>
(v -> k)
-> k
-> k
-> M.Map (GTR.Row k v) (GTR.Row k v)
-> GTR.Row k v
-> M.Map (GTR.Row k v) (GTR.Row k v)
spread1 :: (v -> k)
-> k
-> k
-> Map (Row k v) (Row k v)
-> Row k v
-> Map (Row k v) (Row k v)
spread1 v -> k
fk k
k1 k
k2 Map (Row k v) (Row k v)
hmacc Row k v
row = Row k v
-> Row k v -> Map (Row k v) (Row k v) -> Map (Row k v) (Row k v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert Row k v
rowBase Row k v
kvNew Map (Row k v) (Row k v)
hmacc where
ks :: Set k
ks = [k] -> Set k
forall a. Ord a => [a] -> Set a
S.fromList [k
k1, k
k2]
rowBase :: Row k v
rowBase = Set k -> Row k v -> Row k v
forall k (t :: * -> *) v.
(TrieKey k, Foldable t) =>
t k -> Row k v -> Row k v
GTR.deleteMany Set k
ks Row k v
row
hmv :: Row k v
hmv = Maybe (Row k v) -> Row k v
forall k v. TrieKey k => Maybe (Row k v) -> Row k v
GTR.maybeEmpty (Maybe (Row k v) -> Row k v) -> Maybe (Row k v) -> Row k v
forall a b. (a -> b) -> a -> b
$ Row k v -> Map (Row k v) (Row k v) -> Maybe (Row k v)
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup Row k v
rowBase Map (Row k v) (Row k v)
hmacc
kvNew :: Row k v
kvNew = Maybe (Row k v) -> Row k v
forall k v. TrieKey k => Maybe (Row k v) -> Row k v
GTR.maybeEmpty (Maybe (Row k v) -> Row k v) -> Maybe (Row k v) -> Row k v
forall a b. (a -> b) -> a -> b
$ do
v
k <- k -> Row k v -> Maybe v
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k1 Row k v
row
v
v <- k -> Row k v -> Maybe v
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k2 Row k v
row
Row k v -> Maybe (Row k v)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Row k v -> Maybe (Row k v)) -> Row k v -> Maybe (Row k v)
forall a b. (a -> b) -> a -> b
$ k -> v -> Row k v -> Row k v
forall k v. TrieKey k => k -> v -> Row k v -> Row k v
GTR.insert (v -> k
fk v
k) v
v Row k v
hmv
{-# inline spread1 #-}
groupBy :: (Foldable t, GT.TrieKey k, Eq k, Ord v) =>
k
-> t (GTR.Row k v)
-> M.Map v (Frame (GTR.Row k v))
groupBy :: k -> t (Row k v) -> Map v (Frame (Row k v))
groupBy k
k t (Row k v)
tbl = [Row k v] -> Frame (Row k v)
forall row. [row] -> Frame row
frameFromList ([Row k v] -> Frame (Row k v))
-> Map v [Row k v] -> Map v (Frame (Row k v))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> t (Row k v) -> Map v [Row k v]
forall (t :: * -> *) k v.
(Foldable t, Eq k, TrieKey k, Eq v, Ord v) =>
k -> t (Row k v) -> Map v [Row k v]
groupL k
k t (Row k v)
tbl
groupL :: (Foldable t, Eq k, GT.TrieKey k, Eq v, Ord v) =>
k -> t (GTR.Row k v) -> M.Map v [GTR.Row k v]
groupL :: k -> t (Row k v) -> Map v [Row k v]
groupL k
k t (Row k v)
tbl = (Map v [Row k v] -> Row k v -> Map v [Row k v])
-> Map v [Row k v] -> t (Row k v) -> Map v [Row k v]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' Map v [Row k v] -> Row k v -> Map v [Row k v]
forall k. Ord k => Map k [Row k k] -> Row k k -> Map k [Row k k]
insf Map v [Row k v]
forall k a. Map k a
M.empty t (Row k v)
tbl where
insf :: Map k [Row k k] -> Row k k -> Map k [Row k k]
insf Map k [Row k k]
acc Row k k
row = Map k [Row k k]
-> (k -> Map k [Row k k]) -> Maybe k -> Map k [Row k k]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k [Row k k]
acc (\k
v -> ([Row k k] -> [Row k k] -> [Row k k])
-> k -> [Row k k] -> Map k [Row k k] -> Map k [Row k k]
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith [Row k k] -> [Row k k] -> [Row k k]
forall a. [a] -> [a] -> [a]
(++) k
v [Row k k
row] Map k [Row k k]
acc) (k -> Row k k -> Maybe k
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k Row k k
row)
{-# inline groupL #-}
joinWith :: (Foldable t, Ord v, GT.TrieKey k, Eq v, Eq k) =>
(GTR.Row k v -> [GTR.Row k v] -> [GTR.Row k v])
-> k
-> k
-> t (GTR.Row k v)
-> t (GTR.Row k v)
-> Frame (GTR.Row k v)
joinWith :: (Row k v -> [Row k v] -> [Row k v])
-> k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
joinWith Row k v -> [Row k v] -> [Row k v]
f k
k1 k
k2 t (Row k v)
table1 t (Row k v)
table2 = [Row k v] -> Frame (Row k v)
forall row. [row] -> Frame row
frameFromList ([Row k v] -> Frame (Row k v)) -> [Row k v] -> Frame (Row k v)
forall a b. (a -> b) -> a -> b
$ ([Row k v] -> Row k v -> [Row k v])
-> [Row k v] -> t (Row k v) -> [Row k v]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' [Row k v] -> Row k v -> [Row k v]
insf [] t (Row k v)
table1 where
insf :: [Row k v] -> Row k v -> [Row k v]
insf [Row k v]
acc Row k v
row1 = [Row k v] -> (v -> [Row k v]) -> Maybe v -> [Row k v]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (Row k v -> [Row k v] -> [Row k v]
f Row k v
row1 [Row k v]
acc) v -> [Row k v]
appendMatchRows (k -> Row k v -> Maybe v
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k1 Row k v
row1) where
appendMatchRows :: v -> [Row k v]
appendMatchRows v
v = (Row k v -> Row k v) -> [Row k v] -> [Row k v]
forall a b. (a -> b) -> [a] -> [b]
map (Row k v -> Row k v -> Row k v
forall k v. TrieKey k => Row k v -> Row k v -> Row k v
GTR.union Row k v
row1) [Row k v]
mr2 [Row k v] -> [Row k v] -> [Row k v]
forall a. [a] -> [a] -> [a]
++ [Row k v]
acc where
mr2 :: [Row k v]
mr2 = k -> v -> t (Row k v) -> [Row k v]
forall (t :: * -> *) k v.
(Foldable t, TrieKey k, Eq k, Ord v) =>
k -> v -> t (Row k v) -> [Row k v]
matchingRows k
k2 v
v t (Row k v)
table2
leftOuterJoin :: (Foldable t, Ord v, GT.TrieKey k, Eq v, Eq k) =>
k
-> k
-> t (GTR.Row k v)
-> t (GTR.Row k v)
-> Frame (GTR.Row k v)
leftOuterJoin :: k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
leftOuterJoin = (Row k v -> [Row k v] -> [Row k v])
-> k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
forall (t :: * -> *) v k.
(Foldable t, Ord v, TrieKey k, Eq v, Eq k) =>
(Row k v -> [Row k v] -> [Row k v])
-> k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
joinWith (:)
innerJoin :: (Foldable t, Ord v, GT.TrieKey k, Eq v, Eq k) =>
k
-> k
-> t (GTR.Row k v)
-> t (GTR.Row k v)
-> Frame (GTR.Row k v)
innerJoin :: k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
innerJoin = (Row k v -> [Row k v] -> [Row k v])
-> k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
forall (t :: * -> *) v k.
(Foldable t, Ord v, TrieKey k, Eq v, Eq k) =>
(Row k v -> [Row k v] -> [Row k v])
-> k -> k -> t (Row k v) -> t (Row k v) -> Frame (Row k v)
joinWith Row k v -> [Row k v] -> [Row k v]
seq
matchingRows :: (Foldable t, GT.TrieKey k, Eq k, Ord v) =>
k -> v -> t (GTR.Row k v) -> [GTR.Row k v]
matchingRows :: k -> v -> t (Row k v) -> [Row k v]
matchingRows k
k v
v t (Row k v)
rows = [Row k v] -> Maybe [Row k v] -> [Row k v]
forall a. a -> Maybe a -> a
fromMaybe [] (v -> Map v [Row k v] -> Maybe [Row k v]
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup v
v Map v [Row k v]
rowMap) where
rowMap :: Map v [Row k v]
rowMap = k -> t (Row k v) -> Map v [Row k v]
forall (t :: * -> *) k v.
(Foldable t, Eq k, TrieKey k, Eq v, Ord v) =>
k -> t (Row k v) -> Map v [Row k v]
hjBuild k
k t (Row k v)
rows
{-# INLINE matchingRows #-}
hjBuild :: (Foldable t, Eq k, GT.TrieKey k, Eq v, Ord v) =>
k -> t (GTR.Row k v) -> M.Map v [GTR.Row k v]
hjBuild :: k -> t (Row k v) -> Map v [Row k v]
hjBuild k
k = (Map v [Row k v] -> Row k v -> Map v [Row k v])
-> Map v [Row k v] -> t (Row k v) -> Map v [Row k v]
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' Map v [Row k v] -> Row k v -> Map v [Row k v]
forall k. Ord k => Map k [Row k k] -> Row k k -> Map k [Row k k]
insf Map v [Row k v]
forall k a. Map k a
M.empty where
insf :: Map k [Row k k] -> Row k k -> Map k [Row k k]
insf Map k [Row k k]
hmAcc Row k k
row = Map k [Row k k]
-> (k -> Map k [Row k k]) -> Maybe k -> Map k [Row k k]
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map k [Row k k]
hmAcc (\k
v -> ([Row k k] -> [Row k k] -> [Row k k])
-> k -> [Row k k] -> Map k [Row k k] -> Map k [Row k k]
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
M.insertWith [Row k k] -> [Row k k] -> [Row k k]
forall a. [a] -> [a] -> [a]
(++) k
v [Row k k
row] Map k [Row k k]
hmAcc) (Maybe k -> Map k [Row k k]) -> Maybe k -> Map k [Row k k]
forall a b. (a -> b) -> a -> b
$ k -> Row k k -> Maybe k
forall k v. TrieKey k => k -> Row k v -> Maybe v
GTR.lookup k
k Row k k
row
{-# INLINE hjBuild #-}