将我的代码从OCaml/F#映射到Scala - 一些问题

Question

我在空闲时间学习Scala - 作为一个学习练习,我将一些我在另一个StackOverflow问题中编写的 OCaml代码翻译成Scala.由于我是Scala的新手,我很欣赏一些建议......

但在提出我的问题之前 - 这是原始的OCaml代码:

let visited = Hashtbl.create 200000

let rec walk xx yy =
    let addDigits number =
        let rec sumInner n soFar =
            match n with
            | x when x<10  -> soFar+x
            | x -> sumInner (n/10) (soFar + n mod 10) in
        sumInner number 0 in
    let rec innerWalk (totalSoFar,listOfPointsToVisit) =
        match listOfPointsToVisit with
        | [] -> totalSoFar
        | _ ->
            innerWalk (
                listOfPointsToVisit
                (* remove points that we've already seen *)
                |> List.filter (fun (x,y) ->
                    match Hashtbl.mem visited (x,y) with
                    | true -> false (* remove *)
                    | _    -> (Hashtbl.add visited (x,y) 1 ; true))
                (* increase totalSoFar and add neighbours to list *)
                |> List.fold_left
                    (fun (sum,newlist) (x,y) ->
                        match (addDigits x)+(addDigits y) with
                        | n when n<26 ->
                            (sum+1,(x+1,y)::(x-1,y)::(x,y+1)::(x,y-1)::newlist)
                        | n -> (sum,newlist))
                    (totalSoFar,[])) in
    innerWalk (0,[(xx,yy)])

let _ =
    Printf.printf "Points: %d\n" (walk 1000 1000)

...这是我将其翻译成的Scala代码:

import scala.collection.mutable.HashMap

val visited = new HashMap[(Int,Int), Int]

def addDigits(number:Int) = {
    def sumInner(n:Int, soFar:Int):Int =
      if (n<10)
        soFar+n
      else
        sumInner(n/10, soFar+n%10)
    sumInner(number, 0)
}

def walk(xx:Int, yy:Int) = {
    def innerWalk(totalSoFar:Int, listOfPointsToVisit:List[(Int,Int)]):Int = {
        if (listOfPointsToVisit.isEmpty) totalSoFar
        else {
            val newStep = 
                listOfPointsToVisit.
                // remove points that we've already seen
                filter(tupleCoords => {
                    if (visited.contains(tupleCoords))
                        false
                    else {
                        visited(tupleCoords)=1 
                        true
                    }
                }).
                // increase totalSoFar and add neighbours to list
                foldLeft( (totalSoFar,List[(Int,Int)]()) )( (state,coords) => {
                    val (sum,newlist) = state
                    val (x,y) = coords
                    if (addDigits(x)+addDigits(y) < 26)
                        (sum+1,(x+1,y)::(x-1,y)::(x,y+1)::(x,y-1)::newlist)
                    else
                        (sum,newlist)
                });
            innerWalk(newStep._1, newStep._2)
        }
    }
    innerWalk(0, List((xx,yy)))
}

println("Points: " + walk(1000,1000))

Scala代码编译并正常工作,报告正确的结果.

但...

• 除非我遗漏了什么,否则我在Scala中找不到管道操作符(即|>OCaml和F#),所以我使用了相应的列表方法(filter和fold Left).在这种情况下,最终结果与原始结果非常接近,但我想知道 - 对于功能型解决方案而言,管道运营商不是一种普遍有利且更通用的方法吗？为什么Scala不配备它？

• 在Scala中,我必须专门启动我的折叠状态(这是一个(Int, List[Int,Int])特定类型的空列表的元组.用简单的话说,List()没有削减它 - 我必须明确指定List[(Int,Int)](),否则我得到...相当困难错误消息.我根据上下文对其进行了解密 - 它抱怨了Nothing- 我意识到这个小代码中唯一一个Nothing出现类型的地方可能是我的空列表.但是,与OCaml相比,结果更加丑陋...有什么我能做得更好吗？

• 同样,OCaml能够将折叠的结果元组作为参数传递给innerWalk.在Scala中,我不得不分配一个变量并调用尾递归调用 innerWalk(newStep._1, newStep._2).元组和函数参数之间似乎没有等价 - 即我不能在具有两个参数的函数中传递2-arity的元组 - 同样,我不能将函数的参数元组解析为变量(I不得不明确地在折叠功能体内分配state和coords解构它们.我错过了什么吗？

总的来说,我对结果很满意 - 我会说,如果我们将此示例的OCaml代码分级为100%,那么Scala大约为85-90% - 它比OCaml更冗长,但它更多,更多比Java更接近OCaml.我只是想知道我是否充分利用了Scala,或者是否错过了一些可以改进代码的构造(更有可能).

请注意,我避免将我原来的OCaml模式匹配映射到Scala,因为在这种情况下我觉得它有点矫枉过正 - if两个地方的表达都要清晰得多.

在此先感谢您的任何帮助/建议.

PS旁注 - 我在walk呼叫周围添加了时序指令(从而避免了JVM的启动成本)并测量了我的Scala代码 - 它以OCaml速度的大约50%运行 - 这很有趣,与我获得的速度完全相同Mono执行F#等效代码(如果您关心这种比较,请参阅我原来的SO问题以获取F#代码).由于我目前在企业环境中工作,50%的速度是我很乐意为编写简洁的ML类代码而付出的代价,并且仍然可以访问JVM/.NET生态系统的广泛性(数​​据库,Excel文件生成等) .对不起OCaml,我确实试过你 - 但你不能完全"说"甲骨文 :-)

编辑1:在@senia和@lmm提出建议后,代码得到了显着改善.希望获得@lmm关于foldMap和Shapeless如何另外帮助的更多建议:-)

编辑2:我用scalaz中的flatMap进一步清理了代码 - gist就在这里.不幸的是,这种变化也造成了巨大的10倍放缓-猜,由foldMap完成的连接列表比foldLeft的"添加仅一个新节点"慢得多.想知道如何更改代码以快速添加...

编辑3:在@lmm的另一个建议之后,我将scalaz-flatMap版本从使用转换List为使用immutable.Vector:这有很大帮助,将速度从10x减慢到......只比原始代码慢2倍.那么,干净的代码还是2倍的速度？决定,决定...... :-)

Answer 1

• Scalaz确实提供了一个|>操作员,或者你可以自己编写一个.一般来说,在Scala中对它的需求要少得多,因为对象有一些方法,正如你在一些翻译中看到的那样(例如somethingThatReturnsList.filter(...)你在OCaml中必须写的那些somethingThatReturnsList |> List.filter(...).所以它没有内置到语言中.但如果你需要它,它在那里.
• foldLeft有点普遍; 您可能能够使用例如Scalaz编写更清晰的代码foldMap(在您的元组的情况下,您可能还需要shapeless-contrib,以便派生相应的类型类实例).但基本上是的,Scala类型推断将不如OCaml可靠,你会发现自己必须添加显式类型注释(有时因为不清楚的Nothing错误消息) - 这是我们为允许传统的OO extends继承而付出的代价.
• 您可以使用(innerWalk _).tupled获取一个元组的函数.或者您可以编写函数来接受元组并利用参数自动元组来调用它们而不使用显式元组语法.但是,是的,没有多参数函数的通用编码(你可以使用Shapeless将它们转换成那种形式),我怀疑很大程度上是因为JVM的兼容性.我怀疑如果现在编写标准库它会将HLists用于所有内容,并且普通函数和HList表示之间会有等价,但这将是一种非常难以以向后兼容的方式进行的更改.

你似乎使用了很多ifs,并且你正在做的事情中有一些函数,比如visited.put(tupleCoords, 1)返回一个值是否被替换的布尔值,所以你可以将它用作你整个filter调用的主体.正如我所说,如果你愿意使用Scalaz,foldLeft可以改写为更清晰foldMap.我怀疑整个递归循环可以用命名结构表达,但没有立即想到,所以也许不是.