斯卡拉。語言平坦化功能的實現

我想在Scala中實現平坦化功能。我完成了這樣的事情：斯卡拉。語言平坦化功能的實現

// implementation 
def flatten(xs: List[Any]): List[Any] = 
    xs match { 
     case List() => List() 
     case y::ys => y match { 
      case k::ks => flatten(List(k)) ::: flatten(ks) ::: flatten(ys) 
      case _ => y :: flatten(ys) 
     } 
    } 
// something like tests 
def main(args: Array[String]){ 
    val f1 = flatten(List(List(1, 1), 2, List(3, List(5, 8)))) 
    assert(f1 == List(1, 1, 2, 3, 5, 8)) 
    val f2 = flatten(List(List(List(1), List(1)), 2, List(3, List(5, 8)))) 
    assert(f2 == List(1, 1, 2, 3, 5, 8)) 
}

此實現的工作，但使用的是串聯（它是緩慢的，我認爲）。有人可以提供（或解釋）一個沒有列表連接的解決方案嗎？

我GOOGLE了一點點，但大多數有關內置問題的扁平化

來源

2014-06-07 kharandziuk

丟掉類型不是慣用;-) –

這是更適合codereview.se – Daenyth

@Daenyth，請描述您的筆記。我有一個原子問題，我正確地用代碼示例來描述和說明。什麼原因將其移動到某個地方？ – kharandziuk

對於初學者來說，如@ OM-NOM-NOM指出，確實在談到什麼是地道不解決List[Any]沒有點。讓我們看看我們是否可以用更好的方式來描述它。

sealed trait Tree[A] 
case class Node[A](l: List[Tree[A]]) extends Tree[A] 
case class Leaf[A](a: A) extends Tree[A] 

def flatten[A](tree: Tree[A]): List[A]

現在填寫空白會變得容易一些。

def flatten[A](tree: Tree[A]): List[A] = { 
    def flattenRec(acc: List[A], t: Tree[A]): List[A] = t match { 
    case Leaf(a) => a :: acc 
    case Node(ll) => ll.foldLeft(acc)(flattenRec) 
    } 
    flattenRec(Nil, tree).reverse 
}

但是，如果我們添加一些額外的能力，我們使用Tree scalaz，那麼這變得更容易，實際上可以幫助你做任何你想用列表的扁平名單做。這裏我提供了scalaz.Foldable[Tree]的定義。

import scalaz._ 
import Scalaz._ 

object Tree { 
    implicit def treeFoldable = new Foldable[Tree] { 
    override def foldMap[A, B](fa: Tree[A])(f: (A) => B)(implicit F: Monoid[B]): B = { 
     fa match { 
     case Leaf(a) => f(a) 
     case Node(l) => l.foldLeft(F.zero)((acc, tree) => F.append(acc, foldMap(tree)(f))) 
     } 
    } 

    override def foldRight[A, B](fa: Tree[A], z: => B)(f: (A, => B) => B): B = fa match { 
     case Leaf(a) => f(a, z) 
     case Node(l) => l.foldRight(z)((tree, zz) => foldRight[A, B](tree, zz)(f)) 
    } 
    } 
}

現在我們的扁平化變得簡單

def flatten2[A](tree: Tree[A]): List[A] = { 
    Foldable[Tree].foldLeft(tree, List.empty[A])((acc, a) => a :: acc).reverse 
}

，或者使用可摺疊語法進口

def flatten2[A](tree: Tree[A]): List[A] = { 
    tree.foldLeft(List.empty[A])((acc, a) => a :: acc).reverse 
}

如果我們有Tree[Int]我們可以總結所有的值

val numbers: Tree[Int] = Node(List(Leaf(1), Node(List(Leaf(2), Leaf(3))), Leaf(4))) 
val sum = numbers.foldLeft(0)(_ + _)

就像我事實證明，斯卡拉已經非常類似Tree，我發現了一些非常有用的東西。區別在於scalaz.Tree包含一個A，每個Node[A]。

來源

2014-06-07 15:37:57 drstevens

斯卡拉。語言平坦化功能的實現

回答

相關問題