Haskell: Multiset (Bag) 表示

Question

目前，我正在尝试获取一个整数列表 (Int)，并将它们放入多重集表示中。对于一些背景知识，表示形式如下所示：

*user passes in a list:* [1,2,3,4]
*multiset representation:* [(1,1),(2,1),(3,1),(4,1)]

我写了两个函数：add和del。 add 接受一个整数和一个包，并将整数插入包中。它检查重复项 - 如果有，它只是将计数器（包中坐标的第二个元素）增加 1。然后 returns 那个包。

所以，我的算法应该是：取列表，说[1,2,3,4]；遍历列表中的每个元素 - 对于这些元素中的每一个，调用 add，参数是当前元素和包。对于下一个元素，执行相同的操作 - 传递元素，以及从上一个 add 调用返回的包。

这就是我犹豫不决的地方：我将如何实际编写代码？我已经把我的（不太好）尝试放在下面。我已经完全弄清楚了算法，但不确定如何执行它。任何正确方向的提示都会很棒。

multi :: Eq a => [a] -> Bag a
multi [] = []
multi (x:xs) = ins x []

Answer 1

正如你所说，你已经找到了算法；你几乎可以直接将它翻译成 Haskell:

-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi [] = []
multi (x:xs) =
  -- and for each of these elements, call add with the parameters being the current element
  -- and the bag.
  let returnedBag = add x theBag
  -- For the next element, do the same - pass the element, with the bag that was returned 
  -- from the previous add call.
  in doTheSame xs returnedBag

当然，这不太行得通，因为缺少两个定义：什么是doTheSame，什么是theBag？好吧，我们现在希望 doTheSame 表示 multi 正文中的所有内容，但请注意，我们想将两个参数传递给 doTheSame 而不是 [=19= 的那个] 需要。那么让我们尝试让 doTheSame 成为它自己的函数：

-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts ???
  where
  doTheSame [] theBag = ???
  doTheSame (x:xs) theBag =
    -- and for each of these elements, call add with the parameters being the current element
    -- and the bag.
    let returnedBag = add x theBag
    -- For the next element, do the same - pass the element, with the bag that was returned 
    -- from the previous add call.
    in doTheSame xs returnedBag

这解决了 theBag 的问题——它就是传递给 doTheSame 的任何内容。但是现在我们有一些 ??? 占位符需要填充一些东西。 multi 完成处理元素后应该做什么？ Return它一直在打造的包，毫无疑问：

-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts ???
  where
  doTheSame [] theBag = theBag
  doTheSame (x:xs) theBag =
    -- and for each of these elements, call add with the parameters being the current element
    -- and the bag.
    let returnedBag = add x theBag
    -- For the next element, do the same - pass the element, with the bag that was returned 
    -- from the previous add call.
    in doTheSame xs returnedBag

那么第一个给 doTheSame 的 ??? 呢？那一定是您开始使用的袋子——大概是一个空袋子。（您需要为自己定义什么。）

-- So, my algorithm should be: take the list, say [1,2,3,4];
multi :: Eq a => [a] -> Bag a
-- go through each element in the list
multi elts = doTheSame elts emptyBag
  where
  doTheSame [] theBag = theBag
  doTheSame (x:xs) theBag =
    -- and for each of these elements, call add with the parameters being the current element
    -- and the bag.
    let returnedBag = add x theBag
    -- For the next element, do the same - pass the element, with the bag that was returned 
    -- from the previous add call.
    in doTheSame xs returnedBag

假设您定义了 add 和 emptyBag，此代码有效！但你可能想稍微整理一下。更有经验的 Haskell 程序员可能会使用一些较短的名称，并使 returnedBag 内联：

-- So, my algorithm should be: take the list, say [1,2,3,4]; go through each element in the
-- list - and for each of these elements, call add with the parameters being the current
-- element and the bag. For the next element, do the same - pass the element, with the bag
-- that was returned from the previous add call.
multi :: Eq a => [a] -> Bag a
multi elts = go elts emptyBag
  where go [] bag = bag
        go (x:xs) bag = go xs (add x bag)

此代码与之前的代码完全相同 — 比较喜欢其中一个的唯一原因是您是否发现一个更易于阅读。（永远不要低估能够阅读自己的代码的重要性，也永远不要高估你在一段时间后阅读自己的代码的能力并且在你的脑海中不再新鲜！）

加分项：

这种递归在一般的函数式语言中很常见，通常称为fold。折叠以一些数据（在本例中为空包）开始，遍历列表或类似列表的结构，对于该结构中的每个元素，使用一个函数（在本例中为 add）将数据与元素生成新数据，用于下一个元素，依此类推，返回数据的最终值（在本例中，一个包含所有元素的包）。由于这是一个常见的模式，在 Haskell 中有一个名为 foldl 的函数（对于 left fold，因为您正在从左）只需要一个组合函数、一个初始值和一个列表，并为您完成所有其余工作：

multi :: Eq a => [a] -> Bag a
multi elts = foldl (\bag x -> add x bag) emptyBag elts

虽然您仍在学习递归和 Haskell 的基础知识，但我不会太努力地按照 multi 的最后一个版本的风格编写代码。但是，一旦您完成了几次 where go 技巧并且厌倦了每次都把这些都写出来，那就去查找 foldl 和 foldr 并采取下一步！

Haskell: Multiset (Bag) 表示

Haskell: Multiset (Bag) Representation

haskell

functional-programming

function

bag

multiset