SML сопоставить фильтр? - PullRequest
Новая
       38

SML сопоставить фильтр?

0 голосов
/ 18 декабря 2018

Если у меня есть этот код: 

fun coord_select (x : int, cs : (int*int) list) =
         List.filter (fn (first, _) => first = x ) cs

тестирование с вводом дает это: 

coord_select (2, [(2,2),(2,3),(3,3),(4,3)])
: val it = [(2,2),(2,3)] : (int * int) list

Теперь, что если я не дам желаемую первую координату как * 1007?* но как список нескольких необходимых первых координат, таких как [3,4], т.е. я хочу, чтобы все кортежи координат начинались с 3, а также с 4?Самый простой способ - создать рекурсивную оболочку, которая прошла бы по списку и включила значение в качестве первой переменной coord_select.Но я бы хотел понять вложенные вещи лучше, чем такая грубая сила.Итак, я придумал это: 

fun coord_match (fs : int list, cs :(int*int) list) =
         map (coord_select (f, cs)) fs

, но это не может действительно работать, потому что, как было отмечено, coord_select в map на самом деле пытается вернуть список - и какmap знаете, как подключить членов fs к f?Common Lisp действительно имеет устройство для предотвращения запуска подобных функций, то есть оператор '.Но это опять-таки не поможет, потому что map не знает, какая переменная fs предоставляет.Для ввода, например, у меня есть эти координаты: 

[(2,2),(2,3),(3,3),(4,3)]

, и у меня есть этот список x-координат для сравнения с приведенным выше списком 

[3,4]

Опять же, я мог бы просто поставитьрекурсивная обертка вокруг этого, но я стремлюсь к более элегантному вложенному решению из большого семейства fold.

1 Ответ

0 голосов
/ 20 декабря 2018

что делать, если я не даю желаемую первую координату в виде целого числа, а в виде списка нескольких требуемых первых координат, таких как [3,4], то есть я хочу, чтобы все кортежи координат начинались с 3 и 4

Звучит так, как будто вы хотите, чтобы все кортежи координат начинались с 3 или 4, поскольку координата не может быть и 3 , и 4. * 1009.*

Учитывая это, вы можете написать coord_select как: 

fun member (x, xs) =
    List.exists (fn x2 => x = x2) xs

fun coord_select (xs, coords) =
    List.filter (fn (x, _) => member (x, xs)) coords

большее fold семейство

Это семейство называется катаморфизмы , из которых map, filter, exists и foldl.Поскольку foldl является наиболее общим из них, технически возможно написать код выше, используя сгибы целиком: 

fun coord_select (xs, coords) =
    foldr (fn ((x, y), acc1) =>
      if foldl (fn (x2, acc2) => acc2 orelse x = x2) false xs
      then (x, y) :: acc1
      else acc1) [] coords

, но, как должно быть очевидно, явные сгибы не очень читабельны.

Если есть специализированный комбинатор, который выполняет свою работу, вы бы предпочли это в несколько раз.И если его не существует, создание его из немного менее специализированных комбинаторов улучшает читабельность.Фальцовка настолько близка к ручной рекурсии, что и дает мало информации читателю о том, какую рекурсию мы пытаемся выполнить.

По этой причине я также сделал member из exists, так как exists требует, чтобы я указывал предикат, а мой предикат "равенство с x";так что даже exists, я чувствую, добавляет беспорядок в функцию coord_select.

Вы можете узнать больше о списочных катаморфизмах в функциональном программировании, прочитав Функциональное программирование с бананами, линзами, конвертами и колючей проволокой (1991), Мейер, Фоккинга, Патерсон.

...