最近入了本SICP，发现自己对Lisp没以前那么反感了……好像括号看起来还不错……

starwing83

回复 69# OwnWaterloo


    SCIP在没有引入赋值的基础上就导出了类型系统哦～（不是OO）

starwing83

回复 70# OwnWaterloo


    31.5，贵么？

pandaiam

该如何写递归啊.
我基本上不会写(用c)...

两位指导指导.

比如这个题,
http://poj.org/problem?id=1011

Description
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

Input
输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。

Output
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5Description
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。

Input
输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。

Output
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

做这些题我发现基本上都需要用到递归..但我不会写...
脑子里总是想把所有的情况都想尽,于是解决不下去了,两位空余时间帮帮忙啊..

OwnWaterloo

回复 66# starwing83

最后来回你这个贴……   等会要出门了……  回来希望看到你的oo in sicp啊……


其实我也不是很懂。但暂时不懂的话，也没办法是不是……
比如foldl与foldr，是那个haskell程序员进化里看到的吧？ 那文章我现在都完全当笑话看的……
如果真要看到这文章就马上将里面所有代码搞懂…… 我估计现在都走不出那文章……

抛开这些东西，用过一段时间后，会得到一些直觉反应……
比如curried。 以前我觉得这个概念我完全掌握了……  多简单一个概念啊……

遇到

1. uncurry :: (a -> b -> c) -> (a, b) -> c

复制代码

我就败了……
将一个两参数函数转换成一个单tuple的函数， 如此specific的东西居然出现在Prelude里？
但其实不是……

1. 
   
2. zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
   
3. uncurry zip3 :: ([a], [b]) -> [c] -> [(a, b, c)]
   
4. uncurry $ uncurry zip3 :: (([a], [b]), [c]) -> [(a, b, c)]
   

复制代码

也就是说，以前即使知道这个概念，潜意识里还是将uncurried form翻译为curried form来理解，没能直接从curried form去理解。

再比如 ((. g) . f . g) …… 一开始看到它真是无能为力……
但对curried有一些直觉反应后：

1. 
   
2. ((. g) . f . g) a
   
3. (. g) (f (g a))
   
4. (f (g a)) . g
   
5. 
   
6. ((. g) . f . g) a b
   
7. ((f (g a)) . g) b
   
8. f (g a) (g b)
   

复制代码

就知道它是构造出一个point-free的函数 \a b -> f (g a) (g b)

在这个问题上，curried form的最终效果是不区分application与partial application。
a -> b 就可以被apply一个a， 得到b。 如果b是 c -> d 就还可以继续被apply 一个c， 否则就是值了。
于是再看到foldr模拟foldl就可以直觉反应出，如果硬要写作scheme —— scheme对左fold的定义与haskell不一样 —— 的话：

1. 
   
2. (define lfold
   
3.   (lambda (f acc xs)
   
4.     ( (foldr (lambda (b g) (lambda (x) (g (f x b)))) ; 必须显式 partial application
   
5.              values
   
6.              xs )
   
7.       acc ) ))
   

复制代码

starwing83

回复 73# pandaiam

1. local function dfs(t, idx)
   
2.     if t.equals == t.result then error "ok" end
   
3. 
   
4.     local idx = idx or 1
   
5.     local cur = t[idx]
   
6.     if cur == t.len then
   
7.         t.equals = t.equals + 1
   
8.         dfs(t, idx + 1)
   
9.         t.equals = t.equals - 1
   
10.         return
    
11.     end
    
12. 
    
13.     for i = #t, idx+1, -1 do
    
14.         local res = cur + t[i]
    
15.         if res <= t.len then
    
16.             t[i] = res
    
17.             dfs(t, idx + 1)
    
18.             t[i] = t[i] - cur
    
19.         end
    
20.     end
    
21. end
    
22. 
    
23. local function solve(t)
    
24.     -- find the posible length
    
25.     table.sort(t)
    
26.     t.max = t[#t]
    
27.     t.sum = 0
    
28.     for i, v in ipairs(t) do t.sum = t.sum + v end
    
29.     for i = t.max, t.sum do
    
30.         t.result = t.sum/i
    
31.         if t.result == math.floor(t.result) then
    
32.             t.equals = 0
    
33.             t.len = i
    
34.             if not pcall(dfs,t) then return i end
    
35.         end
    
36.     end
    
37. end
    
38. 
    
39. print(solve {5,2,1,5,2,1,5,2,1,6})
    
40. print(solve {2,3,5,7,11,13,17,19,23})
    
41. print(solve {1,2,3,4})
    
42. 
    
43. 
    

复制代码

starwing83

回复 74# OwnWaterloo


    不大容易，因为要归纳还有点难度。

话说回来把。我觉得haskell和lisp一样都是一种毒品。一旦你习惯了list/curry，再去看C/C++，真是很痛苦的事情，你会觉得自己被限死在一套框子里面出不来的感觉。以前对机器的直觉感觉越来越模糊了。都快记不得CPU，RAM，寄存器，跳转，堆栈这些东西了，脑海中就只有变换，计算这些，感觉是两个世界的存在，一个是机械世界，一个是生物世界。

OwnWaterloo

回复 66# starwing83

再说你那几个问题……

如果要确实回答这些问题， 我现在还是办不到……

我打算先把语言、idoim学到一定程度后 —— 至少还有arrow与FRP（希望这东西能让我对GUI产生一点信心……）其他的就没法管了， 什么都要看paper的语言受不了…… —— 再去研究底层实现。
你应该能理解过早研究底层实现的坏处吧……  看看论坛最近donet8与asker160的发帖吧……  比如用 ((int*)p)[-1] 获取内存块大小……

haskell（或者说GHC）的执行模型与我学过的其他语言完全不一样……
C语言你是学了多久才清楚它的执行模型的？  比如， 才知道尾递归这回事的？
C++又是学了多久才知道如何调教那些特性的？
我这才学3个多月……  换作C/C++的话， 还是在单.cpp的年代啊……

而且，一点都不涉及比语言更底层的 —— 汇编，链接，加载器等等 —— 仅停留在C/C++层面还是无法彻底掌握它们的执行模型。
我觉得haskell同样， 停留在语言层面同样没法确定性的分析出那些地方会消耗多少空间。
而haskell的底层……  GHC产生的C代码你也知道……
GHC还可以产生出一种中间格式，应该比C简单， 但也会干扰haskell的学习……

我现在能够确认的是： foldl' (+) 0 numbers 可以被优化到像循环那样，常数空间。
再比如回文那个题目， 我觉得有方法优化成lua代码那样， 两层循环， 并且tostring还可以保留它的lazy。
也就是3层循环， 2层是产生一个pair， 最里面一层是将tostring展开 —— 够吸引人么？ 代码肯定不如常规的haskell代码那样简洁， 但肯定比等效的C/C++要简洁……
只是这个方法我现在还不会……

最后……  最近haskell学习停了……  又再搞gae……  一方面是因为支持python2.7了……  另一方面是因为猴子的vps貌似到期了……

OwnWaterloo

回复 76# starwing83

>> 你会觉得自己被限死在一套框子里面出不来的感觉。

这话为什么不能反过来说？ 是C/C++将你限制在一套框子里出不去。
以前看到过一种说法， 不记得原话了， 作者让读者去看sicp， 去看scheme， 去感受其他语言给你带来的limitation。


>> 以前对机器的直觉感觉越来越模糊了。都快记不得CPU，RAM，寄存器，跳转，堆栈这些东西了，脑海中就只有变换，计算这些，感觉是两个世界的存在，一个是机械世界，一个是生物世界。

对机器的直觉有那么重要？  不，仅仅是因为你曾经有这个直觉， 所以才会觉得它重要。
你看javaer关心这个么？ 或者其他的纯python， 纯php程序员？

即使你对mov eax, ebx熟悉又怎样？它下层还有东西， 貌似叫mirco instruction？
如果目的是追求底层， 追求本质， 是否要继续去研究这些东西？

编程从来都是一个分层次(layer)的活动，即使是以前那种直接写汇编的先驱，他们依然是在硬件工程师给他们创造的抽象层上工作。
如果仅仅局限于自己一开始接触到的那个层次，认为其他层次都是次品就太狭隘了。

starwing83

回复 78# OwnWaterloo


    不是说重要，也不是说好，但是，你不觉得那种直觉更真实么，特别是haskell，给我一种，恩，在念自己不懂原理的魔咒那种很没有安全感的感觉。我根本不知道编译器会在什么时候跟我抱怨，而C/C++我是知道的。

OwnWaterloo

回复 79# starwing83

你了解各种文件系统的格式么？它们是不是才更真实？ 那 fread会不会让你没有安全感？
再比如git， 了解它的格式确实让人很有安全感……  但平时不会自己去手工操作那些格式吧？

至于编译器的抱怨…… C++也是你现在，学过了才知道了……   才学的时候你也不知道的好哇……
而且你那个写一大堆才去编译的习惯啊……………………

不得不承认的是要将C++/haskell调教成功需要很高的代价……  不一定值得……
反正我目前也只是学来玩而已……  如果成功了就可以实际使用， 不成功也学到了不少东西……