SML Ленивая сортировка списка int с использованием потоков

Вопрос

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

Мы знаем, что сортировка сравнением требует как минимум O(n log n) сравнений, где were сортирует 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'.

Он принимает список целых чисел и возвращает целочисленный поток, представляющий отсортированный список. Это должно быть сделано в постоянное время. Каждый раз, когда поток 'форсируется', он дает либо Empty, либо Cons(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:

(* 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;

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

Любая помощь будет оценена по достоинству.


list sorting lazy-evaluation lazy-sequences sml
person Vasyagamer    schedule 12.03.2011    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

Вы находитесь на правильном пути с функцией размещения (вроде... я не знаю, почему у вас есть типы 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. Я не думаю, что имеет значение меньше или равно (просто меньше, чем должно работать .... действительно не думал об этом). Кроме того, вы должны сначала добраться до конца списка, чтобы сказать, какой из них самый маленький, так что это хвост вперед. так что (* 1 *) является первым, а затем каждый внутренний вызов (* 2 *) до самого внешнего.
  3. Это должно быть cons(x, insertsort xs) в (* 5 *), так как вы возвращаете int stream' с функцией.
person phwd    schedule 16.03.2011

arrow_upward
2
arrow_downward

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

  • вам не нужно преобразовывать список int в поток int». Во-первых, это нарушает правило, согласно которому первоначальный вызов lazysort должен выполняться за константное время. Обратите внимание, что преобразование его в поток int выполняется за линейное время. Что вам нужно сделать, так это предоставить встроенную функцию сортировки в замыкании приостановленного потока, который вы возвращаете (используя блок let). Первый элемент потока будет результатом функции сортировки (выполненной с приостановленным закрытием. ) Второй элемент потока (который является просто потоком int) должен быть вызовом вашей функции отложенной сортировки, потому что она возвращает поток int. Обратите внимание, как это позволяет избежать необходимости его преобразования. Сама функция сортировки довольно проста, потому что вам нужно только найти наименьший элемент и вернуть остальную часть списка без элемента, который вы нашли наименьшим.
person Tim A    schedule 16.03.2011