Использование складки в SML

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

Я пытаюсь написать функцию select, которая использует шаблон сворачивания и принимает функцию и список. Он перенесет заголовок списка в функцию, чтобы определить, добавит ли он этот элемент в список. Вот пример того, что я имею в виду.

          select (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10];
          val it = [2,4,6,8,10] : int list

Итак, вот что у меня есть на данный момент ...

          fun select f l = foldl (fn (x,y) => if (f(x)) then x else 0) 0 l;

Очевидно, это работает неправильно. Он просто возвращает 10. Я уверен, что мне нужно каким-то образом использовать op ::, чтобы заставить это работать, но я не могу этого понять. Я считаю, что это должно выглядеть примерно так ...

          fun select f l = foldl (fn (x,y) => if (f(x)) then op:: else []) [] l;

Но это не работает. Любая помощь будет оценена. Спасибо!


functional-programming sml smlnj
person MCR    schedule 09.03.2012    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Вы близки. Единственные проблемы - это _1 _ / _ 2_ случаи в функции, которую вы передаете fold.

Помните, что в вашем fn (x,y), x - это рассматриваемый вами элемент списка, а y - результат свертывания остальной части списка. Если f(x) не удается, то вы хотите исключить x из результата, поэтому вы просто передаете y. Если f(x) успешно, вы хотите включить x в свой результат, поэтому вы вернете y@[x].

Обратите внимание, что лучше избегать использования оператора добавления (y@[x]) там, где это возможно, поскольку это операция с линейным временем, а добавление (x::y) является постоянным. Конечно, замена одного на другой в этом случае приведет к построению вашего списка в обратном порядке. Вы можете обойти это, также свернувшись назад, то есть используя foldr вместо foldl.

person Nick Barnes    schedule 09.03.2012

arrow_upward
2
arrow_downward

То, что вы реализуете, уже существует. Это называется filter.

- List.filter (fn x => x mod 2 = 0) [1,2,3,4,5,6,7,8,9,10];
val it = [2,4,6,8,10] : int list

Ваша попытка во втором примере кода довольно близка. Я хотел бы указать на несколько проблем:

  • op:: - это оператор, который является функцией. Вероятно, вы не хотите возвращать функцию. Вместо этого вы, вероятно, захотите использовать оператор для создания списка из элемента заголовка и остальной части списка, например: x :: y

  • В другом случае вы в настоящее время возвращаете пустой список и выбрасываете все, что было накоплено в y. Вы, вероятно, не захотите этого делать.

  • Подумайте, какой вариант лучше всего подходит для вывода: левый или правый.

person newacct    schedule 09.03.2012
comment
Спасибо. Я очень ценю твой совет. - person MCR; 09.03.2012