Сведение потока в SML

У меня есть этот тип данных:

datatype 'a stream' = Susp of unit -> 'a stream
and 'a stream = Empty | Cons of 'a * 'a stream'

и я хочу написать функцию сглаживания, которая имеет тип ниже.

flatten: ’a stream’ stream’ -> ’a stream’

Функция flatten будет принимать поток потоков в качестве входных данных и сглаживать их, добавляя их.

Как мне это сделать? Любые идеи?

Спасибо.

Изменить: я знаю, как это сделать для списков. Это довольно просто: fun flatten [] = [] | flat (l::ls) = l @ flatten ls; Помогите мне с потоками, пожалуйста, я не знаю, как сопоставить поток потоку с шаблоном.


functional-programming sml smlnj
person Dave    schedule 25.02.2012    source источник
comment
Я предполагаю, что это домашнее задание. Я предлагаю вам сначала попытаться сгладить список, а затем адаптировать его к потокам.   -  person Andreas Rossberg    schedule 25.02.2012
comment
@AndreasRossberg, я знаю, как это сделать для списков. Это довольно просто: fun flatten [] = [] | flat (l::ls) = l @ flatten ls; Помогите мне с потоками, пожалуйста, я не знаю, как сопоставить поток потоку с шаблоном.   -  person Dave    schedule 25.02.2012
comment
Вы как обычно сопоставляете шаблон: fun flatten Empty = ... | flatten (Cons(x,xs)) = .... Вам также необходимо определить append для потоков. Единственный оставшийся трюк — вставить fn в нужные места.   -  person Andreas Rossberg    schedule 25.02.2012

Ответы (1)


arrow_upward
1
arrow_downward

Сначала напишем для list:

fun append(xs, ys) = case xs of
    [] => ys
  | (x::xs) => x :: append(xs, ys)              

fun flatten(xss) = case xss of
    [] => []
  | (xs::xss) => append(xs, flatten(xss))

Вышесказанное должно быть очевидным. Теперь нам нужно только немного изменить его, чтобы поддерживать stream, с помощью Suspending и force-ing на соответствующих шагах:

fun force(Susp(xs)) = xs()                                        

fun append(xs, ys) = case force xs of
    Empty => ys
  | Cons(x,xs) => Susp(fn () => Cons(x, append(xs, ys)))

fun flatten(xss) = case force xss of
    Empty => Susp(fn () => Empty)
  | Cons(xs,xss) => append(xs, flatten(xss))
person Cactus    schedule 19.03.2016