时间戳

首页 > 解决方案 > Haskell：多集（袋）表示

function - Haskell：多集（袋）表示

问题描述

目前，我正在尝试获取整数列表（Int），并将它们放入多集表示中。对于一点背景，表示将如下所示：

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

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

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

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

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

标签： functionhaskellfunctional-programmingmultisetbag

解决方案

正如您所说，您已经弄清楚了算法；您几乎可以直接将其翻译成 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而不是需要的那个multi。所以让我们尝试制作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怎么做？毫无疑问，归还它一直在建造的包：

-- 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

此代码有效，假设您有addand的定义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)

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

额外学分：

这种递归通常在函数式语言中很常见，通常称为折叠。折叠从一些数据（在本例中为空包）开始，遍历一个列表或类似列表的结构，并且对于该结构中的每个元素，使用一个函数（在本例中为 add）将数据与element 生成新数据，用于下一个元素，依此类推，返回数据的最终值（在这种情况下，一个包含所有元素的包）。由于这是一种常见模式，因此在 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采取下一步行动！

推荐阅读