Haskell Выполнение левого внешнего соединения

Question

Я работаю над назначением uni для реализации левого внешнего соединения в Haskell, используя только определения функции прелюдии. Я попытался с помощью списковых:

ljoin :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b, Maybe c)] 
ljoin xs ys = [if x1 == y1 then (x1,x2, Just y2) else (x1,x2, Nothing)| (x1, x2) <- xs, (y1,y2) <- ys] 

Это производит следующий вывод для примера:

Main> ljoin [(2,"S"),(1,"J")] [(2,1),(2,2),(3,4)] 
[(2,"S",Just 1),(2,"S",Just 2),(2,"S",Nothing),(1,"J",Nothing),(1,"J",Nothing),(1,"J",Nothing)] 
(399 reductions, 834 cells)   

ли кто-нибудь может дать мне какие-либо советы, чтобы избавиться от дублирующих записей в результате? (2, «S», «Ничто») не должно быть в результатах и ​​должно присутствовать только 1 из (1, «J», «Нет»).

Заранее благодарен.

Answer 1

Так что, когда вы делаете [f x y | x <- xs, y <- ys] вы делаете декартово произведение или внутреннее соединение: каждый элемент из xs будет работать в паре с каждым значением от ys. Это не то, что вы хотите.

Что вы хотите, чтобы сначала пройти через все элементы xs, а затем получить список всех значений в ys, которые совпадают, то отправка по поводу того, что последний список является пустым, чтобы включить Nothing, если вам нужно затем, затем соедините x1 и x2 с элементами этого списка, чтобы сделать тройки. Итак, мы начинаем с записью, что «общая стратегия»:

ljoin xs ys = concat [map (adjoin x1 x2) $ handleNulls $ getMatches x1 ys 
          | (x1, x2) <- xs] where 

«CONCAT» необходима, потому что каждый элемент xs будет производить свой собственный список, и мы хотим, чтобы «придавить» их все в один большой список результаты, это единственное, чего не хватает в нашей общей стратегии. Теперь мы заполняем детали:

ljoin xs ys = concat [map (adjoin x1 x2) $ handleNulls $ getMatches x1 ys 
          | (x1, x2) <- xs] where 
    adjoin x1 x2 x3 = (x1, x2, x3) 
    handleNulls zs | null zs = [Nothing] 
        | otherwise = map Just zs 
    getMatches x1 ys = [y2 | (y1, y2) <- ys, y1 == x1] 

В настоящее время существует два способа, которые вы могли бы означать «с использованием только прелюдией определения функций»: это может означать, что вы не разрешили никаких import заявления, но вы позволили сделайте выражение таким сложным, как вам нравится (здраво!), или это может означать, что вы не можете использовать любые другие определения вообще, включая where (безумный!). Я не вижу какой-либо способ сделать последний без обмана для handleNulls шага, но вы можете сортировать «шкурой» накрутки в качестве функции приложения, потому что это не является рекурсивным связывания:

ljoin xs ys = concat [ zip3 (repeat x1) (repeat x2) . 
        (\zs -> if null zs then [Nothing] else map Just zs) . 
        map snd . filter ((x1 ==) . fst) $ ys | (x1, x2) <- xs] 

Но это просто " Тьфу "; предыдущая версия намного понятнее.

Answer 2

Если ключи в ys являются уникальными, то самым простым вариантом будет использовать Prelude.lookup:

ljoin xs ys = [ (kx, x, lookup kx ys) | (kx,x) <- xs ] 

В противном случае, это сводится к тому, что-то вроде этого:

ljoin ((kx,x):xs) ys = (case [ y | (ky, y) <- ys, ky==kx ] of 
          [] -> [(kx, x, Nothing)] 
          ys' -> [(kx, x, Just y') | y' <- ys']) 
         ++ ljoin xs ys 
ljoin [] _ = [] 

Или то же самое, если вы чтобы получить представление об этом:

ljoin xs ys = [ (kx, x, my) | (kx, x) <- xs, my <- case [ y | (ky, y) <- ys, kx==ky ] of { [] -> [Nothing]; ys' -> fmap Just ys'} ] 

Yo и может, конечно, заменить case с функцией сопоставления с шаблоном:

ljoin xs ys = [ (kx, x, my) | (kx, x) <- xs, my <- listToMaybe [ y | (ky, y) <- ys, kx==ky ] ] 
    where listToMaybe [] = [Nothing] 
      listToMaybe ys' = map Just ys'