Как перебирать списки?

Question

Я пытаюсь изучить стандартный мл нового трикотажа, но я не понимаю, как итерировать, хотя списки.

Я пытаюсь создать функцию, которая принимает значение и список функций, и возвращает другой список строк, если текущая функция возвращает значение true при задании значения.

Функция такая как ('a -> bool) * string, т. Е. Пара функций и строка ее имени.

Функция представляет собой функцию карри, поэтому ее определяют как «fun itr x xs».

Я хочу сделать это нерекурсивно.

Может ли кто-нибудь помочь мне начать?

Answer 1

Естественная и простая функция для этого может быть написана достаточно легко с рекурсией.

fun itr x fs = 
    case fs 
    of [] => [] 
    | (f, s) :: fs' => if f x 
         then s :: itr x fs' 
         else itr x fs' 

Или, если вы не хотите явно рекурсии в функции, вы можете использовать foldr.

fun itr x fs = 
    List.foldr (fn ((f, s), ss) => 
    if f x 
    then s :: ss 
    else ss) [] fs 

Кроме того, itr не очень информативно имя, так что вы можете выбрать другой, который лучше описывает то, что вы пытаетесь сделать.

Answer 2

Итак, если я правильно понимаю, вы хотите, чтобы иметь возможность вызывать вашу функцию как это:

itr 
    3 
    [ ((fn i => i > 3), "greaterThanThree"), 
     ((fn i => i mod 2 = 1), "odd"), 
     ((fn i => 12 mod i = 0), "dividesTwelve") 
    ] 

и получить результат, как ["odd", "dividesTwelve"] (с odd и dividesTwelve являются две функции, которые возвращают true при применении до 3).

Есть ли у меня это право?

Таким образом, мы можем начать с написания:

(* Given a value and a list of named Boolean functions, returns a list of the names of the 
* functions that return true for value. 
*) 
fun itr value namedFunctions = 
    ... 

Так вы говорите, что вы хотите «сделать это нерекурсивно», я предполагаю, что вы имеете в виду, что вы хотите использовать функции списка в стандартную базовую библиотеку ML, которая позволяет обрабатывать списки, предоставляя функции, которые обрабатывают элементы списка отдельно; эти функции реализуются с использованием рекурсии, конечно, но если itr просто делегирует их, то itr сам по себе не обязательно должен быть рекурсивным.

Учитывая эти требования, я вижу два подхода.

---

Один подход должен начать с помощью List.filter (see List.filter documentation here), чтобы получить только элементы namedFunctions, которые возвращают true при вызове на value.Для этого нам нужна функция, которая принимает именованную функцию (a ('a -> bool) * string, где 'a - тип value) и возвращает true, если именованная функция возвращает true; то есть:

(* A function that, given a named Boolean function, returns whether it returns true for 
* value. 
*) 
fn (f, _) => f value 

Это позволяет нам называть List.filter так:

(* A list of the elements of namedFunctions that return true for value. *) 
List.filter (fn (f, _) => f value) namedFunctions 

После того, как мы есть, что мы должны использовать List.map (see List.map documentation here), чтобы получить только имя каждой функции:

(* A list of the names in namedFunctions that return true for value. *) 
List.map #2 (List.filter (fn (f, _) => f value) namedFunctions) 

(где #2 - это функция для извлечения компонента 2 кортежа или записи, в случае имени f unction, #2 namedFunction - это имя).

Ввод вместе:

(* Given a value and a list of named Boolean functions, returns a list of the names of the 
* functions that return true for value. 
*) 
fun itr value namedFunctions = 
    List.map #2 (List.filter (fn (f, _) => f value) namedFunctions) 

---

Другой подход заключается в объединении как фильтрацию и отображение в одну стадию, с помощью List.mapPartial (см List.mapPartial documentation here). Вместо того, чтобы сначала выбирать только те элементы, которые нам нужны, используя функцию, которая принимает именованную функцию, и возвращает логическое значение, а затем преобразует их в форму, которую мы хотим, используя функцию, которая принимает именованную функцию и возвращает ее имя, мы можем объединить шаги, используя функцию, которая принимает именованную функцию и возвращает ее имя , только если мы хотим это.

В стандартном ML, когда мы хотим представить значение, которое не всегда существует, мы используем option; например, string option означает «ни строка, ни ничего» (see Option.option documentation here; обратите внимание, что, хотя он задокументирован как Option.option, он также доступен как option). Итак, вот функция, которая принимает указанную функцию и возвращает его имя, только если она возвращает истину для value:

(* A function that, given a named Boolean function, returns its name if it returns true 
* for value, and nothing if it returns false. 
*) 
fn (f, name) => if f value then SOME name else NONE 

Такая функция называется «частичная функция» — она возвращает значение только для части из его домен — и мы можем использовать List.mapPartial, чтобы извлечь его результаты только для тех случаев, когда он возвращает один:

(* Given a value and a list of named Boolean functions, returns a list of the names of the 
* functions that return true for value. 
*) 
fun itr value namedFunctions = 
    List.mapPartial (fn (f, name) => if f value then SOME name else NONE) namedFunctions 

в общем, в любое время, что вы хотите применить List.map к результату List.filter или наоборот, вы можете комбинировать оба шага, используя List.mapPartial. (В любом случае, однако, это может быть или не быть хорошей идеей. Я рекомендую, в зависимости от того, насколько яснее.)