Операторы case и сопоставление с образцом

Я пишу код на SML для задания, решил несколько практических задач и чувствую, что что-то упускаю — мне кажется, что я использую слишком много операторов case. Вот что я делаю, и формулировки проблем, с которыми у меня проблемы.:

  1. Напишите функцию all_except_option, которая принимает строку и список строк. Вернуть NONE, если строки нет в списке, иначе вернуть SOME lst, где lst подобен списку аргументов, за исключением того, что в нем нет строки.

    fun all_except_option(str : string, lst : string list) =
  case lst of 
   [] => NONE
  | x::xs => case same_string(x, str) of
               true => SOME xs
             | false => case all_except_option(str, xs) of
                          NONE => NONE
                        | SOME y=> SOME (x::y)

  2. Напишите функцию get_substitutions1, которая принимает список строк list (список строк, подстановок) и строку s и возвращает список строк. В результате есть все строки, которые есть в каком-то списке в подстановках, в которых тоже есть s, но самой s не должно быть в результате.

    fun get_substitutions1(lst : string list list, s : string) = 
  case lst of
    [] => []
  | x::xs => case all_except_option(s, x) of
                 NONE => get_substitutions1(xs, s)
                | SOME y => y @ get_substitutions1(xs, s)

- same_string - предоставленная функция, fun same_string(s1 : string, s2 : string) = s1 = s2


case functional-programming pattern-matching sml
person user998876    schedule 17.10.2011    source источник
comment
Это часть задания второй недели курса «Языки программирования» от Coursera. Поскольку публикация решений в Интернете является нарушением, я прошу переформулировать этот вопрос, чтобы изменить имена функций, чтобы они не соответствовали точно назначению.   -  person arnab    schedule 21.10.2013

Ответы (3)


arrow_upward
10
arrow_downward

Прежде всего, я бы начал использовать сопоставление с образцом в определении функции вместо оператора case «верхнего уровня». В основном это сводится к тому же самому после десахаризации. Также я бы избавился от аннотаций явного типа, если только это не требуется:

fun all_except_option (str, []) = NONE
  | all_except_option (str, x :: xs) =
    case same_string(x, str) of
      true  => SOME xs
    | false => case all_except_option(str, xs) of
                 NONE   => NONE
               | SOME y => SOME (x::y)

fun get_substitutions1 ([], s) = []
  | get_substitutions1 (x :: xs, s) =
    case all_except_option(s, x) of
      NONE   => get_substitutions1(xs, s)
    | SOME y => y @ get_substitutions1(xs, s)

Если скорость не имеет значения, вы можете объединить два случая в первой функции:

fun all_except_option (str, []) = NONE
  | all_except_option (str, x :: xs) =
    case (same_string(x, str), all_except_option(str, xs)) of
      (true, _)       => SOME xs
    | (false, NONE)   => NONE
    | (false, SOME y) => SOME (x::y)

Но поскольку вы используете append (@) во второй функции и поскольку она не является хвостовой рекурсией, я не думаю, что это ваша главная проблема. Имейте в виду, что добавление является потенциальным «злом», и вы почти всегда должны использовать конкатенацию (а затем обращать свой результат при его возврате) и хвостовую рекурсию, когда это возможно (это всегда так).

Если вам действительно нравятся явные аннотации типов, вы можете сделать это так:

val rec all_except_option : string * string list -> string list option  =
 fn (str, []) => NONE
  | (str, x :: xs) =>
    case (same_string(x, str), all_except_option(str, xs)) of
      (true, _)       => SOME xs
    | (false, NONE)   => NONE
    | (false, SOME y) => SOME (x::y)


val rec get_substitutions1 : string list list * string -> string list =
 fn ([], s) => []
  | (x :: xs, s) =>
    case all_except_option(s, x) of
      NONE   => get_substitutions1(xs, s)
    | SOME y => y @ get_substitutions1(xs, s)

Но это просто мой предпочтительный способ, если мне действительно нужно добавить аннотации типов.

Кстати, а зачем вам функция same_string? Вместо этого вы можете просто сделать сравнение напрямую. Использование вспомогательной функции просто странно, если только вы не планируете в какой-то момент заменить ее какой-то специальной логикой. Однако ваши имена функций не предполагают этого.

person Jesper.Reenberg    schedule 17.10.2011
comment
Когда я пробую верхний блок кода, я получаю ошибки компиляции, говорящие: «Ошибка: оператор не является функцией». ) блокировать. Как я могу сказать sml, что NONE и SOME являются случаями для того, что возвращается all_except_options, а не случаями для get_substitutions? - person Sekm; 03.02.2013
comment
Можно сказать, что ключевое слово fun разделяет две функции. Он работает в SML/NJ 110.72, поэтому либо вы используете другой интерпретатор, либо сделали что-то не так. Вы можете поместить вложенное выражение case в круглые скобки. Однако сообщение об ошибке, которое вы получаете, не похоже на то, что оно имеет какое-либо отношение к случаям? - person Jesper.Reenberg; 05.02.2013
comment
@Jesper.Reenberg Я знаю, что это старая ветка, но я пытаюсь понять, что находится в SOME y в all_except_option. Если вы переключите его на возврат SOME (x::wtf::y), вы увидите, что он выполняется для всех элементов до сопоставления строки, но не для каких-либо элементов после сопоставления строки. Если y содержит оставшуюся часть списка, почему я не вижу дубликата списка? Мне трудно «пройтись» по этой проблеме с блокнотом и отследить, на что НЕКОТОРЫЕ y фактически указывают на каждом шаге. - person mat4nier; 31.10.2016

arrow_upward
1
arrow_downward

В дополнение к тому, что упомянул Jesper.Reenberg, я просто хотел упомянуть, что совпадение bool для true и false можно заменить на if-then-else. Тем не менее, некоторые люди считают if-then-else более уродливым, чем оператор case.

person user102008    schedule 17.10.2011
comment
Правда, я думаю, что я один из тех людей :) - person Jesper.Reenberg; 20.10.2011

arrow_upward

arrow_downward

person    schedule
comment
Всегда есть место для оптимизации if .. then true else false :-) - person Volker Stolz; 27.11.2013