Week5学习笔记

More Function On Lists

写了三个比较有意思的函数，如下

  def removeAt[T](n : Int, xs: List[T]): List[T] = {
    if (n == 0)
      xs match {
        case List() => throw new Error("index out of range!")
        case _::ys => ys
      }
    else
      xs match {
        case List() => throw new Error("index out of range!")
        case x::ys => x :: removeAt(n-1, ys)
      }
  }
  
  def removeAt[T](n : Int, xs : List[T]): List[T] = (xs take n-1) ++ (xs drop n)
  
  // flatMap 操作 
  def flatten[T](xs : List[T]) : List[T] = {
    xs match {
      case List() => List()
      case x :: ys => x match {
        case list: List[T] => flatten(list) ++ flatten(ys)
        case _ => x :: flatten(ys)
      }
    }
  }
  
  // List[T].take(n) 取前n个
  // List[T].drop(n) drop掉前n个取剩下的
  
  def concat[T](xs : List[T], ys : List[T]): List[T] =
    xs match {
      case List() => ys
      case x :: zs => x :: concat(zs, ys)
    }

Pairs and Tuples

  // 归并排序
  def msort(xs: List[Int]): List[Int] = {
    val n = xs.length / 2
    if (n == 0)
      xs
    else {
      def merge(xs: List[Int], ys : List[Int]): List[Int] = {
        (xs, ys) match {
          case (Nil, y) => y
          case (x, Nil) => x
          case (x::x1, y::y1) => if (x < y) x :: merge(x1, ys) else y :: merge(xs, y1)
        }
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst), msort(snd))
    }
  }
  
  // _1 代表第一个元素，_2代表第二个元素，都是逆变参数
  class Tuple2[+T1, +T2](_1: T1, _2:T2) {
      override def toString(): String = "(" + _1 + "," + _2 + ")"
  }

Implicit Parameters

making sort more general
如果我们希望上面的归并排序可以更加general的话，我们会考虑加上泛型参数，但是加上泛型参数之后 < 会报错。

    // 一种方法
  def msort[T](xs: List[T])(lt : (T, T) => Boolean): List[T] = {
    val n = xs.length / 2
    if (n == 0)
      xs
    else {
      def merge(xs: List[T], ys : List[T]): List[T] = {
        (xs, ys) match {
          case (List(), List()) => List()
          case (List(), y) => y
          case (x, List()) => x
          case (x::x1, y::y1) => if (lt(x, y)) x :: merge(x1, ys) else y :: merge(xs, y1)
        }
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst)(lt), msort(snd)(lt))
    }
  }

scala.math.Ordering[T]提供了比较的方法

    // 另一种方法
  def msort[T](xs: List[T])(ord: Ordering[T]): List[T] = {
    val n = xs.length / 2
    if (n == 0)
      xs
    else {
      def merge(xs: List[T], ys : List[T]): List[T] = {
        (xs, ys) match {
          case (List(), List()) => List()
          case (List(), y) => y
          case (x, List()) => x
          case (x::x1, y::y1) => if (ord.lt(x, y)) x :: merge(x1, ys) else y :: merge(xs, y1)
        }
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst)(ord), msort(snd)(ord)
    }
  }
  
  // 值得一提的是，Ordering类中有很多现成的 Ordering 子类使用
  trait IntOrdering extends Ordering[Int] {
    def compare(x: Int, y: Int) = java.lang.Integer.compare(x, y)
  }
  implicit object Int extends IntOrdering with CachedReverse[Int]
  
  msort(nums)(Ordering.Int)

定义隐式参数即加入关键字 implicit

  def msort[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
    val n = xs.length / 2
    if (n == 0)
      xs
    else {
      def merge(xs: List[T], ys : List[T]): List[T] = {
        (xs, ys) match {
          case (List(), List()) => List()
          case (List(), y) => y
          case (x, List()) => x
          case (x::x1, y::y1) => if (ord.lt(x, y)) x :: merge(x1, ys) else y :: merge(xs, y1)
        }
      }

      val (fst, snd) = xs splitAt n
      merge(msort(fst), msort(snd))
    }
  }

如果一个函数有一个隐式参数类型为T，编译器会寻找一个隐式定义

  • is marked implicit.
  • has a type compatible with T.
  • is visible at the point of the function call, or is defined in a companion object associated with T.

否则，it's an error.

High-order List Functions

高阶函数

函数式编程语言允许程序员写一些generic函数去实现一些通用模式，这就是高阶函数。

  // 一些有意思的函数 
  def pack[T](xs : List[T]): List[List[T]] = xs match {
    case List() => List()
    case x :: _ => {
      val (first, rest) = xs span (y => y == x)
      first :: pack(rest)
    }
  }

  def encode[T](xs : List[T]) : List[(T, Int)] = pack(xs).map(x => (x.head, x.length))

记录一些比较好用的函数

  • xs filterNot p == xs filter (x => !p(x))
  • xs partition p == (xs filter p, xs filterNot p)
  • xs takeWhile p 最长前缀满足条件的列表
  • xs dropWhile p
  • xs span p == (xs takeWhile p, xs dropWhile p)

Reduction of Lists

上面所讨论的都是一种类似map映射的转换，但是还有另一种常用的操作是combines the elements of a list using a given operator. reduce/fold combinators

    def sum(xs : List[Int]) = (0::xs) reduceLeft (_+_)
    def product(xs : List[Int]) = (1::xs) reduceLeft (_*_)
    
    // a more general function : foldLeft 
    def sum(xs : List[Int]) = (xs foldLeft 0) (_+_)
    def product(xs : List[Int]) = (xs foldLeft 1) (_*_)

    // 代码实现 foldLeft 和 foldRight
    
  def reduceLeft(xs: List[T])(op: (T, T) => T): T = xs match {
    case Nil => throw new Error("Nil.reduceLeft")
    case x :: xs => foldLeft(xs)(x)(op)
  }

  def foldLeft[U](xs: List[T])(z: U)(op: (U, T) => U): U = xs match {
    case Nil => z
    case x :: xs => foldLeft(xs)(op(z, x))(op)
  }

  def reduceRight(xs: List[T])(op: (T, T) => T): T = xs match {
    case Nil => throw new Error("Nil.reduceLeft")
    case x :: Nil => x
    case x :: xs => foldRight(xs)(x)(op)
  }

  def foldRight[U](xs: List[T])(z: U)(op: (U, T) => U): U = xs match {
    case Nil => z
    case x :: xs => op(foldRight(xs)(z)(op), x)
  }
  
  def concat(xs: List[T], ys: List[T]): List[T] =
    (xs foldRight ys) (_ :: _)

  def mapFun[T, U](xs: List[T], f: T => U): List[U] =
    (xs foldRight List[U]()) ((a, b) => f(a) :: b)

  def lengthFun[T](xs: List[T]): Int =
    (xs foldRight 0) ((_, u) => u + 1)

当满足结合律和交换律的时候，foldLeft和foldRight是得到相同结果的(尽管它们的效率是不一样的).

object Test {  // 加入一些测试

  def mapFun[T, U](xs: List[T], f: T => U): List[U] =
    (xs foldRight List[U]()) ((a, b) => f(a) :: b)

  def lengthFun[T](xs: List[T]): Int =
    (xs foldRight 0) ((_, u) => u + 1)

  def main(args: Array[String]): Unit = {
    val a = Array(1, 2, 3)
    val b = 1 +: a
    println(b.toList) // List(1, 1, 2, 3)

    val c = List(1, 2, 3, 4, 5)
    println(mapFun(c, (x : Int) => x + 1))      // List(2, 3, 4, 5, 6)
    println(lengthFun(c))        // 5
  }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 213,928评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,192评论 3赞 387
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 159,468评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,186评论 1赞 286
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,295评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,374评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,403评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,186评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,610评论 1赞 306
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,906评论 2赞 328
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,075评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,755评论 4赞 337
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,393评论 3赞 320
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,079评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,313评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,934评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,963评论 2赞 351

推荐阅读更多精彩内容

  • PEP8, Python代码书写风格指导
    Introduction This document gives coding conventions for t...
    wuutiing阅读 4,539评论 0赞 9
  • 等级之我见
    2018年11月27日星期二多云 日更已上瘾，我决定从今天开始，若时间充裕，第一件事就是日更。 等级，现在和将来都...
    蓝色老虎3阅读 286评论 3赞 5
  • 无媚花
    顺墙一架紫薇花， 不用人管它自爬。 此花开在冬春季， 多少款爷都爱它。
    一马凭原阅读 646评论 7赞 15
  • 私有链的搭建
    1.geth的安装 https://geth.ethereum.org/docs/install-and-buil...
    H_f129阅读 1,175评论 0赞 0