Я пытаюсь найти режим или значение, которое встречается чаще всего. Я хочу такую функцию, как:
mode:' 'a list -> (''a * int) list
и он возвращает режим и место его возникновения, если нет ничьей, а затем возвращает все вхождения, например:
mode([1,1,2,3,5,8]) ===> [(1,2)]
mode([1,3,5,2,3,5]) ===> [(3,2),(5,2)]
mode([true,false,true,true]) ====>[(true,3)]
Я пытаюсь сделать это без библиотечных функций в SML.
пока что я получил:
fun mode(L)=
if null L then nil
else if hd L= hd (tl L) then 1+mode(hd(tl L))
else mode(tl L);
Я знаю, что это неправильно. Думаю, мне любопытно, как вы оба сохраняете индексы того, где встречается режим и что это за режим, и возвращаете их в виде кортежей в списке.
Вы пытаетесь решить упражнение, состоящее из многих частей, с несколькими более простыми упражнениями перед ним. Судя по вашему нынешнему прогрессу, не думали ли вы о решении каких-то очень похожих упражнений, ведущих к конечной цели? Обычно это хороший совет при решении задач программирования: сведите текущую задачу к более простым задачам и решите их.
Создайте histogram : ''a list -> (''a * int) list
над элементами списка:
fun histogram [] = ...
| histogram (x::xs) = ...
Сделайте это, вставив каждый x
с его count
в гистограмму.
fun insert (x, []) = ...
| insert (x, (y, count) :: hist) = ...
И напишите несколько тестов, которые вы можете выполнять время от времени.
Найдите mode : ''a list -> ''a
списка:
fun mode xs = ... (histogram xs)
Сделайте это, найдя элемент на гистограмме с наибольшим количеством:
fun findMax [] = ... (* what if the list/histogram is empty? *)
| findMax [(x, count)] = ...
| findMax ((x, count) :: (y, count) :: hist) = ...
Когда вы хорошо разбираетесь в рекурсивном представлении и навигации по обычным гистограммам, вы можете создать аннотированный histogram : (''a * int * int list) list
, который не только содержит частоту каждого элемента, но и их позиции во входном списке:
fun histogram_helper ([], _) = ...
| histogram_helper (x::xs, i) = ... histogram_helper (xs, i+1) ...
Сделайте это, вставив каждый x
с его count
и позицией i
вместе с ранее найденными позициями is
в гистограмму:
fun insert (x, i, []) = ...
| insert (x, i, (y, count, is) :: hist) = ...
Найдите (возможно, несколько) mode : ''a list -> (''a * int list) list
списка:
fun mode xs = ... (histogram xs)
Сделайте это, найдя (возможно, несколько) элементов на гистограмме с наибольшим количеством:
fun findMax ([], countMax, tmpModes) = ...
| findMax ((x, count, is) :: hist, countMax, tmpModes) = ...
где countMax : int
- это частота, повторяющаяся в tmpModes : (''a * int * int list) list
. Здесь countMax
и tmpModes
— это накопление параметров результата. Сделайте это, определив, следует ли отбросить (x, count, is)
в пользу всех tmpModes
, или добавить к tmpModes
, или выбрать в пользу всех tmpNodes
I am curious on how you both keep the indices of where the mode occurs and what the mode is and return them as tuples in a list.
Да это не банально. Используя предложенное мной разделение на подзадачи, ответ на этот вопрос зависит от того, находимся ли мы в функции histogram
или в функции findMax
:
В histogram
вы можете хранить индексы как часть кортежа, содержащего элемент и частоту. В findMax
, поскольку вы потенциально собираете несколько результатов, вам нужно отслеживать как самую высокую частоту (countMax
), так и выбранные режимы временный (tmpModes
); подлежит замене или добавлению в более позднем рекурсивном вызове.
Итак, чтобы ответить на ваш вопрос: в накопительном параметре.
fun mode(L)= if null L then nil else if hd L= hd (tl L) then 1+mode(hd(tl L)) else mode(tl L);
Используйте сопоставление с образцом вместо null
, hd
и tl
:
fun count_4s [] = 0
| count_4s (x::xs) = (if x = 4 then 1 else 0) + count_4s xs
fun count_ns ([], _) = 0
| count_ns (x::xs, n) = (if x = n then 1 else 0) + count_ns (xs, n)
fun count_12 ([], ones, twos) = (ones, twos)
| count_12 (x::xs, ones, twos) =
if x = 1 then count_12 (xs, ones+1, twos) else
if x = 2 then count_12 (xs, ones, twos+1) else
count_12 (xs, ones, twos)
fun count_abc ([], result) = result
| count_abc (x::xs, ((a, ca), (b, cb), (c, cc))) =
count_abc (xs, if x = a then ((a, ca+1), (b, cb), (c, cc)) else
if x = b then ((a, ca), (b, cb+1), (c, cc)) else
if x = c then ((a, ca), (b, cb), (c, cc+1)) else
((a, ca), (b, cb), (c, cc)))
Построение гистограммы является своего рода расширением этого, где вместо фиксированного значения, такого как 4
, или фиксированного их количества, такого как ones
и twos
, у вас есть целый их список, и вы должны динамически искать тот, который у вас есть. got, x
, и определите, нужно ли добавить его к гистограмме или увеличить на гистограмме.
Лучше всего было бы сделать это во вспомогательной функции, например, если count_abc
было создано во вспомогательной функции,
fun insert_abc (x, ((a, ca), (b, cb), (c, cc))) =
if x = a then ((a, ca+1), (b, cb), (c, cc)) else
if x = b then ((a, ca), (b, cb+1), (c, cc)) else
if x = c then ((a, ca), (b, cb), (c, cc+1)) else
((a, ca), (b, cb), (c, cc)))
fun count_abc ([], result) = result
| count_abc (x::xs, result) =
count_abc (xs, insert (x, result))
только вместо представления гистограммы
(''a * int) * (''a * int) * (''a * int)
ты хочешь
(''a * int) list
и insert
должен быть рекурсивным, а не повторяющимся insert_abc
.