Я нашел этот код в другом посте ТАК:
fun number_in_month ([], _) = 0
| number_in_month ((_,x2,_) :: xs, m) =
if x2 = m then
1 + number_in_month(xs, m)
else
number_in_month(xs, m)
и к моему удивлению это работает.
- number_in_month ([(2018,1,1),(2018,2,2),(2018,2,3),(2018,3,4),(2018,2,30)],2);
val it = 3 : int
Меня смущает сначала незнание этой формы классической математической рекурсивной функции (я новичок), а затем то, как она на самом деле проходит через список. Моя интуиция предполагала рекурсивные вызовы в if-then-else
отправке хвоста списка, т.е.
...
1 + number_in_month((tl xs), m)
...
но это не работает. Как он перебирает список с каждым рекурсивным вызовом? Я могу только представить, что это какая-то встроенная магия SML.
Никакого волшебства, xs
является хвост списка.
Есть две вещи, которые нужно понять: списки и сопоставление с образцом.
В SML синтаксис списка [a, b, c]
— это просто сокращение для a :: b :: c :: nil
, где ::
— это (инфиксный) конструктор cons. Кроме этого сокращения, в списках SML нет ничего волшебного, они предопределены как этот тип:
datatype 'a list = nil | :: of 'a * 'a list
infixr 5 ::
Последнее определение превращает ::
в правоассоциативный инфиксный оператор приоритета 5.
Во-вторых, определение использует сопоставление с образцом для аргумента. Шаблон, подобный x::xs
, соответствует (непустому) списку той же формы, привязывая x
к началу списка, а xs
к его концу, что соответствует приведенному выше определению. В вашей функции x
также заменен другим шаблоном.
Это все. Никакой магии. Это также будет работать с пользовательским представлением списка:
datatype my_list = empty | cons of (int * int * int) * my_list
infixr 5 cons
fun count (empty, x) = 0
| count ((_,y,_) cons xs, x) =
if x = y then 1 + count (xs, x) else count (xs, x)
val test = count ((1,2,3) cons (3,4,5) cons (6,2,7) cons empty, 2)
Так что да, я изменил ...((_,x2,_) :: xs, m)
на ...((x1,x2,x3) :: xs, m)...
, и это сработало, но это похоже на тупик. Боюсь, я упускаю здесь более глубокий принцип. . . .
Если вы хотите использовать всю тройку, назовите ее в шаблоне, заменив (_,x2,_)
только одной переменной: ... | match_month (date :: xs, m) = let val (_,x2,_) = date in ... date :: match month_ (xs, m)
. Вы также можете назвать подшаблон напрямую, используя ключевое слово as
: ((date as (_,x2,_)) :: xs, m)
.
But how could this be changed to, say, build a new list of matches rather than just counting them?
В этом случае вам нужны две модификации вашего текущего решения:
Вы хотите изменить шаблон вашего рекурсивного случая на тот, где вы можете извлечь весь кортеж из трех дат, если он совпадает. Прямо сейчас вы только извлекаете часть месяца для сравнения, отбрасывая другие биты, поскольку вы просто хотите увеличить счетчик в случае совпадения месяца.
Результатом функции должно быть не 1 + ...
, а скорее (x1,x2,x3) :: ...
.
Итак, быстрое решение:
fun dates_of_month ([], _) = []
| dates_of_month ((year,month,day) :: dates, month1) =
if month = month1
then (year,month,day) :: dates_of_month (dates, month1)
else dates_of_month (dates, month1)
I changed
...((_,x2,_) :: xs, m)
to...((x1,x2,x3) :: xs, m)...
and it worked, but that seems like a kludge.
Вот две альтернативы, предложенные Андреасом Россбергом:
Используя пускай-в-конец:
fun dates_of_month ([], _) = []
| dates_of_month (date :: dates, month1) =
let val (_, month, _) = date
in
if month = month1
then date :: dates_of_month (dates, month1)
else dates_of_month (dates, month1)
end
Использование as
:
fun dates_of_month ([], _) = []
| dates_of_month ((date as (_,month,_)) :: dates, month1) =
if month = month1
then date :: dates_of_month (dates, month1)
else dates_of_month (dates, month1)
И вот третий вариант, который абстрагирует рекурсию с помощью комбинатора списков более высокого порядка:
fun dates_of_month (dates, month1) =
List.filter (fn (_, month, _) => month = month1) dates
Это отличный материал. Я слежу за курсы.cs.вашингтон.эду/курсы/cse341/18au, который, ИМХО, является хорошим введением в ML. Подумываю подарить и школьникам. Но сначала я должен освоить его сам.
Ну конечно; естественно. Вот почему
(tl xs)
было ерундой. Но как это можно изменить, чтобы, скажем, построить новый список совпадений, а не просто их подсчитывать? Для этого я бы хотел, чтобы случай nil возвращал[]
, тогда с случаем...((_,x2,_) :: xs, m)
мне нужно было бы получить голову - что это? Это неx
, и(_,x2,_) :: match_month (xs, m)
тоже неправильно. К чему будет привязан заголовок этого входящего списка?