SML: рекурсия LookSay - PullRequest
Новая
       9

SML: рекурсия LookSay

1 голос
/ 01 марта 2020

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

(*lookSay:int list=>int*int list
ENSURE: true
REQUIRE: computes the look-and-say sequence, for example list of l=[2,2,2] which would be read as "three twos"  =>[(2,1),(1,2)] *)

вот мой код: 

    fun lookSay(x:int list)=
    case x of
    []=>[]
      | l::ls =>
    let fun helper(l,l'::ls',acc)=
              if l=l'
              then helper(l,ls',acc+1)
              else (acc,l)::lookSay(ls)
    in
        helper(l,ls,1)
    end

Я не понимаю, почему это не работает. решение, предлагаемое другими, использует вспомогательную функцию runWith (x, L) возвращает (повторяется, хвост): но я не знаю, как это решение получится .. 

    fun runWith (_:int, [] : int list) : int list * int list = ([], [])
  | runWith (x, y::L) =
    if x = y then
      let
        val (repeats, tail) = runWith(x, L)
      in
        (x::repeats, tail)
      end
    else
      ([], y::L)

1 Ответ

0 голосов
/ 02 марта 2020

Я бы начал с форматирования вашего решения следующим образом: 

fun lookSay [] = []
  | lookSay (x::xs) =
    let
      fun helper(y, z::zs, count) =
          if y = z
          then helper(y, zs, count + 1)
          else (count, y) :: lookSay zs
    in
      helper(x, xs, 1)
    end

Я использовал x, y и z вместо l и l', потому что я обнаружите, что l может быть трудно читать: я не могу легко увидеть, является ли это строчными буквами L, прописными буквами i или 1. Поскольку мы на самом деле также используем константу 1, это добавляет путаницу.

Я также сделал несколько переименований переменных: у вас есть одна пара l и ls в поле case-of, и другая пара с таким же именем пара l и ls внутри вспомогательной функции, которая скрывает внешние переменные. Хотя это работает, это очень запутанно, потому что разные вещи в непосредственной близости называются одинаковыми.

Подобным образом я переименовал acc в count, чтобы уточнить, что он накапливает.

Как намекнул molbdnilo Ваша проблема заключается в отсутствующем сопоставлении с образцом. Компилятор ML должен предупредить вас об этом: 

! Toplevel input:
! ..........helper(y, z::zs, count) =
!           if y = z
!           then helper(y, zs, count + 1)
!           else (count, y) :: lookSay zs
! Warning: pattern matching is not exhaustive

Что намекает на то, что helper также должен иметь шаблон [].

Что касается стратегии этого решения: Внутренний * Функция 1031 * делает две вещи, которые требуют внутренней вспомогательной функции. Во-первых, у него есть дополнительный аргумент для «текущего» элемента, который я назвал y, а во-вторых, у него есть накопительный аргумент, который я назвал count. В частности, helper вызывает lookSay, а не себя.

Но только второй из них действительно необходим, поскольку вы также можете использовать заголовок аргумента списка, чтобы сохранить «текущий» элемент: 

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) count =
        if x = y
        then go (x::zs) (count + 1)
        else (count + 1, x) :: go (y::zs) 0
  in
    go xs 0
  end

Эта стратегия просматривает сразу два первых элемента списка, x и y, и, если они равны, отбрасывает один, но увеличивает count. Если x и y не равны, это означает конец последовательности x с, поэтому элемент (count + 1, x) испускается и go может рекурсивно вызывать себя для y::zs.

Я сохранил ошибку, которая также присутствует в вашем примере. В моей версии подсказка molbdnilo может быть перефразирована как «Подумайте о том, как функция go обрабатывает списки с одним элементом».

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

fun concatMap f xs =
    List.concat (List.map f xs)

fun flatten pairs =
    concatMap (fn (n, x) => [n, x]) pairs

fun lookSay xs =
  let
    fun go [] _ = []
      | go (x::y::zs) i =
        if x = y
        then go (x::zs) (i+1)
        else (i+1,x) :: go (y::zs) 0
  in flatten (go xs 0) end

Если предположить, что ошибка исправлена, это должно дать вам: 

- lookSay [1, 1, 1, 2, 2, 3];
> val it = [3, 1, 2, 2, 1, 3] : int list
...