SML рекурсивная функция по списку - PullRequest
Новая
       20

SML рекурсивная функция по списку

0 голосов
/ 19 мая 2019

Я нашел этот код в другом SO сообщении: 

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)

и, к моему удивлению, это работает.Форма классической математической рекурсивной функции (я новичок), а затем, как она на самом деле шагает по списку.Моя интуиция имела бы рекурсивные вызовы в if-then-else, отправляющих хвост списка, то есть 

...
1 + number_in_month((tl xs), m)
...

, но это не работает.Как это перебирает список с каждым рекурсивным вызовом?Я могу только представить, что это какая-то магия SML.

Ответы [ 2 ]

1 голос
/ 20 мая 2019

Но как это можно изменить, скажем, для создания нового списка совпадений, а не просто для их подсчета?

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

  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)

Я изменил ...((_,x2,_) :: xs, m) на ...((x1,x2,x3) :: xs, m)..., и это сработало, но это похоже на кучу.

Вот две альтернативы Андреаса Россберга:

Использование let-in-end : 

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
1 голос
/ 19 мая 2019

Без магии, 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)
...