SML - получить определенный элемент из списка без использования List.nth - PullRequest
Новая
       11

SML - получить определенный элемент из списка без использования List.nth

0 голосов
/ 03 октября 2018

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

Это написать функцию, которая принимает int и список, возвращает определенныйэлемент в списке по индексу заданного int.Как видите, это похоже на функцию List.nth ().

Теперь мне любопытно.Вот как далеко я зашёл, но я просто не могу придумать, как нацелиться на определенный индекс вручную. 

fun nth(nil, _)     = 0
  | nth(x::xs, 0)   = x;
  | nth(x::xs, y)   = 

val list = [1, 2, 3];
nth(list, 0);

1 Ответ

0 голосов
/ 03 октября 2018

Как предположил Джон, индексирование пустого списка может вызвать исключение вместо возврата 0. Это заставляет nth работать для любого типа списка, а не только для подмножества int list s, для которого 0 можно разумно считать "нет"результат".Кажется, что функции не хватает рекурсии для работы с любым индексом, кроме 0. Вот шаблон для работы: 

fun nth ([], _) = raise Empty
  | nth (x::_, 0) = x
  | nth (_::xs, n) = ...

Здесь добавлено исключение, и переменные, которые не будут использоваться в каждом случаефункция была отключена псевдопеременной _.Вам также может понадобиться более информативное сообщение об ошибке. 

fun nth ([], n) = raise Fail "Failed to find the appropriate index!"
  | nth (x::_, 0) = x
  | nth (_::xs, n) = ...

«Более безопасная» версия nth имеет тип 'a list * int -> 'a option, то есть для nth (xs, i), если xs имеет i th элемент x, он возвращает SOME x, а если нет, то возвращает NONE: 

fun nth_safe ([], _) = NONE
  | nth_safe (x::_, 0) = SOME x
  | nth_safe (_::xs, n) = ...

Это "безопаснее", потому что не выдает исключение, если списокне достаточно долго.Пример состязательности: nth ([0,1,2], 3)

Но он все равно не обрабатывается, если индекс отрицательный.Пример состязательности: nth ([0,1,2], ~1)

Вы можете решить эту проблему внутри ... тела третьей функции с помощью if n < 0 then ..., но тогда это будет выполняться на каждом рекурсивном шаге, даже если вы, скорее всего,нужно только проверить его один раз.

Надежная версия этой функции вызывает ошибку, когда вы передаете ей отрицательный индекс.В противном случае ваша функция может вызвать отрицательный цикл до тех пор, пока у вас не закончится память, поскольку рекурсивный случай (третий случай) не сходится к двум базовым случаям (случай 1 и 2).Для версии на основе исключений вы можете написать: 

exception IndexError of int
fun nth (xs, n) =
    let fun go ([], _) = raise IndexError n
          | go (x::_, 0) = x
          | go (_::ys, i) = ...
    in if n < 0 then raise IndexError n else go (xs, n)
    end

Надежная версия, использующая типы данных с учетом ошибок, может выглядеть следующим образом: 

fun nth (xs, n) =
    let fun go ([], _) = NONE
          | go (x::_, 0) = SOME x
          | go (_::ys, i) = ...
    in if n < 0 then NONE else go (xs, n)
    end

И надежная версия, использующая ошибки-Знающие типы данных, которые фиксируют ошибку индекса, как и основанная на исключении версия с пользовательским исключением IndexError, выглядят так: 

datatype ('a, 'b) either = Left of 'a | Right of 'b
fun nth (xs, n) =
    let fun go ([], _) = Left n
          | go (x::_, 0) = Right x
          | go (_::ys, i) = ...
    in if n < 0 then Left n else go (xs, n)
    end

val example_1 = nth ([2,3,5], 5)  (* gives: Left 5  *)
val example_2 = nth ([2,3,5], ~1) (* gives: Left ~1 *)
val example_3 = nth ([2,3,5], 2)  (* gives: Right 5 *)
...