scala-Problem06-10

P06 Find out whether a list is a palindrome

要求

案

P07 Flatten a nested list structure

要求

案

P08 Eliminate consecutive duplicates of list elements

要求

案

P09 Pack consecutive duplicates of list elements into sublists

要求

案

P10 Run-length encoding of a list

要求

案

*声明*このシリーズの記事は次のとおりです.http://aperiodic.net/phil/scala/s-99/ほとんどの内容は原文と同じで、一部の自分のコードが入っています.権利侵害があれば、直ちに本人に連絡してください.本人は直ちに関連内容を削除します.
P06 (*) Find out whether a list is a palindrome.
要求
リストが返事かどうかを判断する
Example:

scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true

イニシアチブ

(1)listを反転する後と自己反転する前の要素の順序は一致する

.

def isPalindrome1[T](list: List[T]): Boolean =
    list == list.reverse

P07 (**) Flatten a nested list structure.
要求
N重リストを埋め込んだリストのすべての要素を新しいリストに抽出します.新しいリストはリスト構造をネストできません.
Example:

scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8)

イニシアチブ

(1)再帰+List.flatMap

def flatten(list: List[Any]): List[Any] = list.flatMap {
    case ls: List[_] => flatten(ls)
    case e           => List(e)
}

P08 (**) Eliminate consecutive duplicates of list elements.
要求
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.
Example:

scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)

イニシアチブ

(1) List.dropWhile + recursive

def compressRecursive[T](list: List[T]): List[T] = list match {
    case Nil       => Nil
    case h :: tail => h :: compressRecursive(tail.dropWhile(e => e == h))
}

(2) List.dropWhile + tail-recursive

def compressTailRecursive[T](list: List[T]): List[T] = {
    def compressR(ret: List[T], ls: List[T]): List[T] = ls match {
        case Nil       => ret
        case h :: tail => compressR(ret ::: List(h), ls.dropWhile(_ == h))
    }

    return compressR(Nil, list)
}

(3) List.dropWhile + tail-recursive

def compressTailRecursive2[T](list: List[T]): List[T] = {
    def compressR(ret: List[T], ls: List[T]): List[T] = ls match {
        case Nil       => ret.reverse
        case h :: tail => compressR(h :: ret, ls.dropWhile(_ == h))
    }

    return compressR(Nil, list)
}

(4) foldRight

def compressFunctional[A](ls: List[A]): List[A] =
    ls.foldRight(List[A]()) { (h, r) =>
        if (r.isEmpty || r.head != h)
            h :: r
        else
            r
    }

P09 (**) Pack consecutive duplicates of list elements into sublists.
要求
If a list contains repeated elements they should be placed in separate sublists.
Example:

scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

イニシアチブ

(1)span+通常再帰

def pack2[T](list: List[T]): List[List[T]] = list match {
    case Nil => List(List())
    case ls: List[T] => {
        val (packed, tail) = ls.span(_ == ls.head)
        if (tail == Nil)
            List(packed)
        else packed :: pack2(tail)
    }
}

(2)span+テール再帰

def pack[T](list: List[T]): List[List[T]] = {
    def packR(ret: List[List[T]], ls: List[T]): List[List[T]] = ls match {
        case Nil => ret
        case head :: tail => {
            val (l, r) = (head :: tail).span(_ == head)
            packR(ret ::: List(l), r)
        }
    }
    return packR(Nil, list)
}

P10 (*) Run-length encoding of a list.
要求
Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as tuples (N, E) where N is the number of duplicates of the element E.
Example:

scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

イニシアチブ

(1) map

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