閱讀1005 返回首頁    go 阿裏雲 go 技術社區[雲棲]

Ruby中實現stream

  流是通過延時求值實現的，Ruby中實現stream也是可以做到，可惜就是沒有尾遞歸優化。按照sicp，首要的是兩個函數：delay和force：
def mem_proc(exp)
  alread_run=false
  result=false
  lambda{
    if !alread_run
      result=exp.call
      alread_run=true
      result
    else
      result
    end
  }
end
def force(delayed_object)
  delayed_object.call
end
def delay(exp)
  mem_proc(lambda{exp})
end
    delay函數返回延時對象，就是對於未來某個時間求值表達式的承諾；force函數以延時對象為參數，進行相應的求值工作，這裏的mem_proc用於記憶已經求值過的表達式。定義stream的constructor和selector函數：
def cons_stream(a,b)
  return a,delay(b)
end
def stream_car(s)
  s[0]
end
def stream_cdr(s)
  force(s[1])
end
def stream_null?(s)
  s.nil? or s==[]
end
    用Ruby中的數組充當“粘合劑”，stream_car直接返回第一個元素，而stream_cdr需要用force求值表達式，履行承諾。另外，將空數組[]作為the-empty-stream。再定義幾個高階函數，map和foreach，其他如filter與此類似：
def stream_enumerate_interval(low,high)
  if low>high
    return []
  else
    cons_stream(low,stream_enumerate_interval(low.succ,high))     
  end
end
def stream_ref(s,n)
  if n==0
    stream_car(s)
  else
    stream_ref(stream_cdr(s),(n-1))     
  end
end
def stream_map(proc,s)
  if stream_null?(s)
    []
  else
    cons_stream(proc.call(stream_car(s)),stream_map(proc,(stream_cdr(s))))    
  end
end
def stream_for_each(proc,s)
  if stream_null?(s)
    :done
  else
    proc.call(stream_car(s))
    stream_for_each(proc,stream_cdr(s))     
  end
end
def display_stream(s)
  stream_for_each(lambda{|item| puts item},s)
end
def stream_filter(pred,s)
  if stream_null?(s)
    []
  elsif pred.call(stream_car(s))
    cons_stream(stream_car(s),stream_filter(pred,stream_cdr(s)))
  else
    stream_filter(pred,stream_cdr(s))   
  end
end

    最後，看下例子：
puts "s:"
s=stream_enumerate_interval(1,5)
display_stream(s)
puts "odd_s:"
odd_s=stream_filter(lambda{|x| x%2==1},s)
display_stream(odd_s)
puts "ss:"
ss=stream_map(lambda{|x|x*x},s)
display_stream(ss)
文章轉自莊周夢蝶  ，原文發布時間2008-05-08

最後更新：2017-05-17 18:01:46

  上一篇：go  sicp3.5.2、3.5.3節部分習題嚐試解答
  下一篇：go  使用Rope來高效處理長字符串