函數(shù)式編程如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃和記憶化搜索?

love_wisdom

函數(shù)式編程如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃和記憶化搜索?

MMMIX

回復(fù) 1# love_wisdom


    https://wiki.haskell.org/Dynamic_programming_example

OwnWaterloo

同學(xué)你最近也問(wèn)了不少問(wèn)題了。。。  都不太好回答啊。。。
“函數(shù)式編程”或“函數(shù)式編程語(yǔ)言”并沒(méi)有一個(gè)很公式化的定義。。。
你能說(shuō)下具體是哪個(gè)編程語(yǔ)言嗎。。。

love_wisdom

回復(fù) 3# OwnWaterloo


    standard ml

OwnWaterloo

回復(fù) 4# love_wisdom
SML：
1. 嚴(yán)格求值
2. 不強(qiáng)調(diào)純函數(shù)
3. 有while
其實(shí)和傳統(tǒng)語(yǔ)言差不多吧， 該怎么實(shí)現(xiàn)就怎么實(shí)現(xiàn)。

關(guān)于while， 不記得這是SML語(yǔ)言標(biāo)準(zhǔn)還是某個(gè)實(shí)現(xiàn)的擴(kuò)展了。
同樣， 也不記得尾調(diào)用優(yōu)化是不是SML語(yǔ)言標(biāo)準(zhǔn)要求的。

如果有while， 那用while肯定沒(méi)什么問(wèn)題。
如果沒(méi)有， 那就要寫(xiě)成尾遞歸形式， 這可能就是和傳統(tǒng)語(yǔ)言不一樣的地方了。
然后靠語(yǔ)言實(shí)現(xiàn)優(yōu)化這個(gè)尾遞歸。 如果不能優(yōu)化又不支持while， 這個(gè)語(yǔ)言實(shí)現(xiàn)就可以丟了， 沒(méi)法用的。

love_wisdom

回復(fù) 5# OwnWaterloo


    我經(jīng)過(guò)上網(wǎng)搜索，看到下面的網(wǎng)址里有尾遞歸的代碼
http://www.cs.cornell.edu/Course ... itations/rec05.html
就是弄不清怎么是尾遞歸了

love_wisdom

回復(fù) 5# OwnWaterloo


    standard ml可以是饑餓求值，也可是命令式的編程范式

OwnWaterloo

回復(fù) 6# love_wisdom

1. 
   
2. fun sum (l:int list):int =
   
3.   case l of
   
4.     [] => 0
   
5.   | x::xs => x + (sum xs)
   

復(fù)制代碼

1. 
   
2. fun sum' (acc:int) (l:int list):int =
   
3.   case l of
   
4.     [] => acc
   
5.   | x::xs => sum' (acc+x) xs
   

復(fù)制代碼

sum和sum' 都會(huì)遞歸調(diào)用自己。 sum里的遞歸不是尾遞歸， 而sum'是。

SICP里有兩張圖。


這張與sum類似。 只是求的是乘積。


與sum'類似， 求的也是乘積。

love_wisdom

如何實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃？