Read Sean

Read me, read Sean.
posts - 508, comments - 655, trackbacks - 9, articles - 4

用Scala解Hanoi塔

Posted on 2009-11-23 19:20 laogao 阅读(2350) 评论(3)  编辑  收藏 所属分类: On JavaProgramming in GeneralOther Languages

到处吹嘘Scala很长时间了,却一直没有在自己的blog上增加过任何相关内容,今天就来补一补。当然,Scala的基本特性就不多废话了,网上已经有相当多的资料,如果懒得google,只想看完本文,那么你只需要知道它是一门以JVM为目标运行环境的静态编程语言(当然,Scala官方也有.NET版,但已不是其重点),同时具备面向对象和函数式编程语言的特点。本文将通过一个简单的示例,展示Scala的FP能力,其中十分heavy的用到了implicit隐式转换和模式匹配。

代码是从guithub的gist上抄的,简单改了改,原始代码见: http://gist.github.com/66925

import scala.reflect.Manifest
  
def simpleName(m:Manifest[_]):String 
= {
  val name 
= m.toString
  name.substring(name.lastIndexOf(
'$')+1)
}
  
trait Num
final class Succ[Pre<:Num] extends Num
final class _1 extends Num
type _2 
= Succ[_1]
type _3 
= Succ[_2]
type _4 
= Succ[_3]
 
case class Move[N<:Num,A,B,C]()

implicit def move1[A,B,C](implicit a:Manifest[A], b:Manifest[B]) : Move[_1,A,B,C] 
= {
  System.out.println(
"Move from " + simpleName(a) + " to " + simpleName(b))
  
null
}
 
implicit def moveN[P
<:Num,A,B,C](implicit m1:Move[P,A,C,B], m2:Move[_1,A,B,C], m3:Move[P,C,B,A]) : Move[Succ[P],A,B,C] = null
  
def run[N
<:Num,A,B,C](implicit m:Move[N,A,B,C]) = null
  
case class Left()
case class Center()
case class Right()
  
run[_3,Left,Right,Center]

 

这段代码解决的是经典的汉诺塔问题,通过一根中柱,将左柱上64个大小依次叠加的圆盘全部移动到右柱,要求整个过程中每次只能移动一个圆盘,且每个圆盘只能独立占据一根柱子或是叠加在比自身更大的圆盘上。

简单分析一下就知道,这是一个递归问题(FP的英雄特长):

  • 当只有1个圆盘时,不用通过中柱,直接可以从左柱移动到右柱;
  • 当有2个圆盘时,将小盘移动到中柱,剩下的大盘移动到右柱,再从中柱把小盘移动到右柱;
  • 当有3个圆盘时,先移动2个圆盘到中柱,再移动大盘到右柱,再移动2个圆盘到右柱;
  • ...

很容易发现一个pattern,那就是移动N(N>1)个圆盘,可以通过以下三个步骤:

  1. 移动N-1个圆盘,从左柱到中柱;
  2. 移动剩下的1个圆盘,从左柱到右柱;
  3. 移动N-1个圆盘,从中柱到右柱。

在解释代码之前,先说说Scala的implicit隐式转换,这是一个非常powerful的idea,当Scala编译器发现类型不匹配,它不会直接fail,而是尝试从代码中指定的,在scope内的implicit转换定义,来替换问题对象或表达式以满足类型要求,当然,为了避免歧义,同一时刻Scala需要找到唯一的一个满足条件的implicit定义。

我们的代码首先定义了一个取得友好类名的方法,不去深究它,然后定义了一个正整数的序列,也不去深究它了,你只需要当作他们是正整数就好,接触过FP的同学应该对此类定义不陌生,接下来定义了如下3个支持implicit传入参数的方法:

  1. implicit def move1[A,B,C](implicit a:Manifest[A], b:Manifest[B]) : Move[_1,A,B,C]
  2. implicit def moveN[P<:Num,A,B,C]( implicit
    m1:Move[P,A,C,B],
    m2:Move[_1,A,B,C],
    m3:Move[P,C,B,A]
    ) : Move[Succ[P],A,B,C]
  3. def run[N<:Num,A,B,C](implicit m:Move[N,A,B,C])

含义分别是:

  1. 当需要Move[_1,A,B,C]值时,可以找我帮忙(我有个side-effect,那就是输出移动指令);
  2. 当需要Move[Succ[P],A,B,C]时,可以找我帮忙;
  3. 运行我,我接受Move[N,A,B,C]类型的参数。

简单说明:Scala用[]表示类型参数,区别于Java的<>,另外,Scala的类型声明在变量/函数定义之后。Move[_,A,B,C]的含义是通过C,从A移动圆盘到B。

我们来模拟运行一下,为了演示效果,用一个中等复杂的数目,3个圆盘,从Left移动到Right。

run[_3,Left,Right,Center],对应Move[Succ[_2],Left,Right,Center],于是展开成三个Move:

Move[_2,Left,Center,Right]即Move[Succ[_1],Left,Center,Right]
Move[_1,Left,Right,Center]
Move[_2,Center,Right,Left]即Move[Succ[_1],Center,Right,Left]

然后继续展开Move[_2,Left,Center,Right]和Move[_2,Center,Right,Left],得到:

Move[_1,Left,Right,Center]
Move[_1,Left,Center,Right]
Move[_1,Right,Center,Left]
--------------------------
Move[_1,Left,Right,Center]
--------------------------
Move[_1,Center,Left,Right]
Move[_1,Center,Right,Left]
Move[_1,Left,Right,Center]

这个时候已经全部都匹配Move[_1,A,B,C],于是我们很容易得到以下输出:

Move from Left to Right
Move from Left to Center
Move from Right to Center
Move from Left to Right
Move from Center to Left
Move from Center to Right
Move from Left to Right

希望本文能带给Scala初学者一些感性认识和启发。


Feedback

# re: 用Scala解Hanoi塔  回复  更多评论   

2009-11-24 16:28 by 大胃
欢迎大家参与讨论,我会不定期删除自言自语式的、软广告式的、和主题无关的、没有营养的回复。

# re: 用Scala解Hanoi塔  回复  更多评论   

2010-06-11 16:18 by 大胃
新发表一篇文章,欢迎前往讨论
http://laogao.me/blog/view/8

# re: 用Scala解Hanoi塔  回复  更多评论   

2012-05-18 23:14 by Freewind
我谨代表群内171位scalaer,热切希望你加入到scala热情交流群: 132569382(QQ群)

只有注册用户登录后才能发表评论。


网站导航: