Haskell: представление Multiset (Bag)

Как вы сказали, вы выяснили алгоритм; вы можете перевести его почти прямо на 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

Этот код работает, если у вас есть определение 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)

Этот код в точности такой же, как и предыдущий - единственная причина предпочесть один другому - это то, легче ли вам его читать. (Никогда не недооценивайте важность возможности читать свой собственный код и никогда не переоценивайте свою способность делать это по прошествии некоторого времени, когда это уже не свежо в вашей памяти!)

Дополнительный кредит:

Этот вид рекурсии очень распространен в функциональных языках в целом и обычно называется сверткой. Сворачивание начинается с некоторых данных (в данном случае пустого мешка), проходит по списку или структуре, подобной списку, и для каждого элемента в этой структуре использует функцию (в данном случае добавление) для объединения данных с element для создания новых данных, которые используются в следующем элементе и т. д., возвращая окончательное значение данных (в данном случае мешок со всеми вашими элементами). Поскольку это распространенный шаблон, в Haskell есть функция с именем foldl (для сгиба слева, поскольку вы обрабатываете элементы списка, начиная слева), которая принимает только функцию комбинирования, начальную value и список, а всю остальную работу сделает за вас:

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

Пока вы все еще изучаете рекурсию и основы Haskell, я бы не стал слишком стараться написать код в стиле той последней версии multi. Но как только вы проделали where go трюк несколько раз и вам надоело все это писать каждый раз, посмотрите foldl и foldr и сделайте следующий шаг!