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. Затем возвращает эту сумку.

Итак, мой алгоритм должен быть следующим: взять список, скажем, [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 вместо того, который принимает 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 inline:

-- 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 . Сгиб начинается с некоторых данных (в данном случае пустого пакета), проходит по списку или структуре, подобной списку, и для каждого элемента в этой структуре использует функцию (в данном случае, добавить) для объединения данных с элемент для создания новых данных, который используется на следующем элементе и т. д., возвращающий окончательное значение данных (в данном случае, мешок со всеми вашими элементами). Так как это обычный шаблон, в Haskell есть функция с именем foldl (для сгиб влево , так как вы обрабатываете элементы списка, начиная с левого), которая принимает только функцию объединения, Начальное значение, а также список, и делает всю остальную работу за вас:

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

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