SML Ленивый вид списка int с использованием потоков - PullRequest
Новая
       73

SML Ленивый вид списка int с использованием потоков

2 голосов
/ 12 марта 2011

вопрос

1 Потоки и ленивая оценка (40 баллов)

Мы знаем, что сортировка сравнений требует, по крайней мере, O (n log n) сравнений, где была сортировка n элементов. Допустим, нам нужны только первые элементы f (n) из отсортированного списка для некоторой функции f. Если мы знаем, что f (n) асимптотически меньше log n, тогда было бы расточительно сортировать весь список. Мы можем реализовать отложенную сортировку, которая возвращает поток, представляющий отсортированный список. Каждый раз, когда к потоку обращаются, чтобы получить заголовок отсортированного списка, наименьший элемент находится в списке. Это занимает линейное время. После удаления элементов f (n) из списка потребуется O (nf (n)). Для этого вопроса мы используем следующие определения типов данных. Также определены некоторые вспомогательные функции. 

(* Suspended computation *)
datatype 'a stream' = Susp of unit -> 'a stream

(* Lazy stream construction *)
and 'a stream = Empty | Cons of 'a * 'a stream'

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

Q1.1 (20 баллов) Реализовать функцию lazysort: int list -> int stream '.

Он принимает список целых чисел и возвращает поток int ', представляющий отсортированный список. Это должно быть сделано в постоянное время. Каждый раз, когда поток «принудительно», он выдает либо «Пустой», либо «Минус» (v, s ') В случае с минусами v является наименьшим элементом из отсортированного списка, а s 'является потоком', представляющим оставшийся отсортированный список. Сила должна занимать линейное время. Например: 

- val s = lazysort( [9, 8, 7, 6, 5, 4] );
val s = Susp fn : int stream'
- val Cons(n1, s1) = force(s);
val n1 = 4 : int
val s1 = Susp fn : int stream'
- val Cons(n2, s2) = force(s1);
val n2 = 5 : int
val s2 = Susp fn : int stream'
- val Cons(n3, s3) = force(s2);
val n3 = 6 : int
val s3 = Susp fn : int stream'

Соответствующие определения

Вот что указано в коде: 

(* Suspended computation *)
datatype 'a stream' = Susp of unit -> 'a stream

(* Lazy stream construction *)
and 'a stream = Empty | Cons of 'a * 'a stream'

(* Lazy stream construction and exposure *)
fun delay (d) = Susp (d)
fun force (Susp (d)) = d ()

(* Eager stream construction *)
val empty = Susp (fn () => Empty)
fun cons (x, s) = Susp (fn () => Cons (x, s))

(*
Inspect a stream up to n elements 
take : int -> 'a stream' -> 'a list
take': int -> 'a stream -> 'a list
*)
fun take 0 s = []
| take n (s) = take' n (force s)
and take' 0 s = []
| take' n (Cons (x, xs)) = x::(take (n-1) xs)

Моя попытка решения

Я попытался сделать следующее, чтобы получить список int и преобразовать его в int stream ': 

(* lazysort: int list -> int stream' *)
fun lazysort ([]:int list) = empty
| lazysort (h::t) = cons (h, lazysort(t));

Но при вызове force он не возвращает минимальный элемент. Я должен искать минимум, но я не знаю, как ... Я думал о выполнении вставки вроде как: 

fun insertsort [] = []
| insertsort (x::xs) =
let fun insert (x:real, []) = [x]
| insert (x:real, y::ys) =
if x<=y then x::y::ys
else y::insert(x, ys)
in insert(x, insertsort xs)
end;

Но мне нужно искать минимум и не сортировать список, а затем помещать его в виде потока ...

Буду признателен за любую помощь.

Ответы [ 2 ]

2 голосов
/ 16 марта 2011

Я в вашем классе и думаю, что вы идете по этому пути совершенно неправильно. Я решил вопрос, но я думаю, что для меня немного неэтично полностью поделиться с вами кодом. Тем не менее, вот указатель:

  • вам не нужно преобразовывать список int в поток int '. Во-первых, это нарушает правило, согласно которому первоначальный вызов lazysort должен выполняться за постоянное время. Обратите внимание, что преобразование его в поток int 'выполняется за линейное время. Вам нужно предоставить встроенную функцию сортировки в закрытии возвращаемого приостановленного потока (используя блок let.) Первый элемент потока будет результатом функции сортировки (выполненной с приостановленным закрытием). Второй элемент потока (который является просто потоком int) должен быть вызовом вашей функции lazysort, потому что он возвращает поток int '. Обратите внимание, как это позволяет вам избежать его преобразования. Сама функция сортировки довольно проста, потому что вам нужно только найти наименьший элемент и вернуть остаток списка без элемента, который вы считаете наименьшим.
2 голосов
/ 16 марта 2011

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

Вы находитесь на правильном пути с функцией размещения (вроде ... я не знаю, почему у вас есть real типов вместо int, когда будет только int streams. Ваш шаблон не будет соответствовать, если вы еще не реализовали). 

   fun insertsort ([]:int list) = empty  
   | insertsort (h::t) =  
    let   
        fun insert (x:real, []) = [x] (* 1 *)
        | insert (x:real, y::ys) =    (* 2 *)
            if x<=y then x::y::ys     (* 3 *)
            else y::insert(x, ys)     (* 4 *)
    in insert(x, insertsort xs)       (* 5 *)

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

  1. У вас должен быть только один аргумент
  2. Iне думайте, что важно иметь меньше или равно (просто меньше, чем должно работать ... на самом деле не думал об этом).Также вы должны сначала добраться до нижней части списка, чтобы определить, какая из них наименьшая, так что это хвост.так что (* 1 *) является первым, затем каждым внутренним вызовом (* 2 *) до самого внешнего.
  3. Это должно быть cons(x, insertsort xs) in (* 5 *), так как вы возвращаете int stream' с функцией.
...