Упражнение number_in_month (рекурсивная функция SML при взаимодействии со списком)

Я нашел этот код в другом посте ТАК:

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.

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
0
128
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Никакого волшебства, 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)

Ну конечно; естественно. Вот почему (tl xs) было ерундой. Но как это можно изменить, чтобы, скажем, построить новый список совпадений, а не просто их подсчитывать? Для этого я бы хотел, чтобы случай nil возвращал [], тогда с случаем ...((_,x2,_) :: xs, m) мне нужно было бы получить голову - что это? Это не x, и (_,x2,_) :: match_month (xs, m) тоже неправильно. К чему будет привязан заголовок этого входящего списка?

147pm 20.05.2019 04:28

Так что да, я изменил ...((_,x2,_) :: xs, m) на ...((x1,x2,x3) :: xs, m)..., и это сработало, но это похоже на тупик. Боюсь, я упускаю здесь более глубокий принцип. . . .

147pm 20.05.2019 04:35

Если вы хотите использовать всю тройку, назовите ее в шаблоне, заменив (_,x2,_) только одной переменной: ... | match_month (date :: xs, m) = let val (_,x2,_) = date in ... date :: match month_ (xs, m). Вы также можете назвать подшаблон напрямую, используя ключевое слово as: ((date as (_,x2,_)) :: xs, m).

Andreas Rossberg 20.05.2019 08:21

But how could this be changed to, say, build a new list of matches rather than just counting them?

В этом случае вам нужны две модификации вашего текущего решения:

  1. Вы хотите изменить шаблон вашего рекурсивного случая на тот, где вы можете извлечь весь кортеж из трех дат, если он совпадает. Прямо сейчас вы только извлекаете часть месяца для сравнения, отбрасывая другие биты, поскольку вы просто хотите увеличить счетчик в случае совпадения месяца.

  2. Результатом функции должно быть не 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. Подумываю подарить и школьникам. Но сначала я должен освоить его сам.

147pm 20.05.2019 18:08

Другие вопросы по теме