函数式编程如何实现动态规划和记忆化搜索?

love_wisdom

函数式编程如何实现动态规划和记忆化搜索?

MMMIX

回复 1# love_wisdom


    https://wiki.haskell.org/Dynamic_programming_example

OwnWaterloo

同学你最近也问了不少问题了。。。  都不太好回答啊。。。
“函数式编程”或“函数式编程语言”并没有一个很公式化的定义。。。
你能说下具体是哪个编程语言吗。。。

love_wisdom

回复 3# OwnWaterloo


    standard ml

OwnWaterloo

回复 4# love_wisdom
SML：
1. 严格求值
2. 不强调纯函数
3. 有while
其实和传统语言差不多吧， 该怎么实现就怎么实现。

关于while， 不记得这是SML语言标准还是某个实现的扩展了。
同样， 也不记得尾调用优化是不是SML语言标准要求的。

如果有while， 那用while肯定没什么问题。
如果没有， 那就要写成尾递归形式， 这可能就是和传统语言不一样的地方了。
然后靠语言实现优化这个尾递归。 如果不能优化又不支持while， 这个语言实现就可以丢了， 没法用的。

love_wisdom

回复 5# OwnWaterloo


    我经过上网搜索，看到下面的网址里有尾递归的代码
http://www.cs.cornell.edu/Course ... itations/rec05.html
就是弄不清怎么是尾递归了

love_wisdom

回复 5# OwnWaterloo


    standard ml可以是饥饿求值，也可是命令式的编程范式

OwnWaterloo

回复 6# love_wisdom

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

复制代码

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

复制代码

sum和sum' 都会递归调用自己。 sum里的递归不是尾递归， 而sum'是。

SICP里有两张图。


这张与sum类似。 只是求的是乘积。


与sum'类似， 求的也是乘积。

love_wisdom

如何实现动态规划？