2012-02-25 3 views
1

에서 스트림을 편평 나는이 데이터 형식이 있습니다는 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; 도와주세요. 제발 스트림의 스트림과 패턴을 매치시키는 방법을 모르겠습니다.

+0

나는이 숙제입니다 가정합니다. 먼저 목록 목록을 병합 한 다음 스트림에 적용하는 것이 좋습니다. –

+0

@AndreasRossberg, 목록을 작성하는 방법을 알고 있습니다. 아주 간단합니다 :'fun flatten [] = [] | flat (l :: ls) = l @ flatten ls;' 스트림을 도와주세요. 스트림의 스트림과 패턴을 맞추는 방법을 모르겠습니다. – Dave

+1

평소와 같이 패턴을 매칭합니다 :'fun flatten Empty = ... | flatten (Cons (x, xs)) = ...'. 또한 스트림에'append'을 정의 할 필요가 있습니다. 유일한 나머지 트릭은'fn'을 올바른 위치에 삽입하는 것입니다. –

답변

1

의 첫 번째 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))    

위 명백해야한다. 이제 우리는 적절한 단계에서 -ing로 끝나는 Suspforce에 의해, stream을 지원하기 위해 약간 변경해야합니다

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))