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", Nothing) 不应该出现在结果中，只有 (1, "J", Nothing) 项中的 1 个应该出现。

提前致谢。

Answer 1

如果 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'} ]

当然可以用模式匹配函数代替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'

Answer 2

因此，当您执行 [f x y | x <- xs, y <- ys] 时，您正在执行 笛卡尔积 或 内连接 ：来自 [=14 的每个元素=] 将与 ys 的每个值配对。这不是你想要的。

你想要的是首先遍历 xs 的所有元素，然后得到 ys 中所有匹配的值的列表，然后调度后一个列表是否是null，在需要时包含 Nothing，然后将 x1 和 x2 连接到该列表的元素以构成三元组。所以我们开始写 "general strategy":

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

"concat" 是必需的，因为 xs 的每个元素都会产生自己的列表，我们希望将它们全部 "flatten" 到一个大的结果列表中，这是唯一的我们的总体战略中缺少的东西。现在我们填写详细信息：

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]

现在有两种方式可以表示 "using only the prelude function definitions"：这可能意味着您不允许使用任何 import 语句，但您可以根据需要使表达式尽可能复杂（理智！），或者这可能意味着您根本不允许任何其他定义，包括where（疯了！）。我看不出有什么方法可以在不对 handleNulls 步骤作弊的情况下完成后者，但是您可以将 "hide" 作弊作为函数应用程序，因为它不是递归绑定：

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]

但这只是 "yuck"；之前的版本清晰多了

Haskell 实现左外连接

Haskell Implement left outer join

haskell

left-join