Lập bản đồ trên các danh sách con trong Scala

Question

Tôi biết rằng hàm bản đồ lấy từng phần tử của một danh sách (một chuỗi) và áp dụng một hàm cho nó. Đệ quy (và không có liên quan đến điều kiện chấm dứt, vv)

map(s, f) = f(s.head) :: map(s.tail, f) 

Tôi đang tìm kiếm một chức năng nào giống như

foo(s, f) = f(s) :: map(s.tail, f). 

Vì vậy, một 'mapper', nơi các chức năng lập bản đồ được gọi vào danh sách con và không các yếu tố riêng lẻ. Nói cách khác, tôi đang tìm một danh sách bản đồ, trái ngược với một bản đồ. Có một cái gì đó như thế này tồn tại, hoặc tôi phải cuộn của riêng tôi (hoặc sử dụng đệ quy)?

Ngoài ra, tôi muốn có một hàm mang theo như là đầu vào một chuỗi và trả về một chuỗi các subsequences giữa-to-end, tức là

bar(s, f) = s :: bar(s.tail, f) 

Answer 1

/* Cách tiếp cận này xác định mapList về phương thức hữu ích khác được gọi là đuôi. Giống như Daniel, tôi sẽ đặt nó trong một phần mở rộng ngầm vào danh sách, nhưng điều đó hoàn toàn là một vấn đề của hương vị */

implicit def richerList[A](list : List[A]) = new { 

/* Đây là một phương pháp gọi là đuôi mà trả mỗi đuôi có thể trong danh sách. Nó là đệ quy đuôi vì vậy nó sẽ không thổi lên trên danh sách lớn. Lưu ý rằng nó hơi khác với chức năng Haskell cùng tên. Phiên bản Haskell luôn thêm một danh sách trống vào kết quả */

def tails : List[List[A]] = { 
    def loop(ls : List[A], accum : List[List[A]]) : List[List[A]] = ls match { 
     case _ :: tail => loop(tail, ls :: accum) 
     case _ => accum 
    } 

    loop(list, Nil).reverse 
    } 

/* Đây là những gì sử dụng đuôi trông giống như

scala> "abc".toList.tails 
res0: List[List[Char]] = List(List(a, b, c), List(b, c), List(c)) 

*/

/* Bây giờ chúng ta có thể xác định mapList dựa trên đuôi */

def mapList[B](f : List[A] => B) = tails map f 
} 

/* Và đây là những gì sử dụng mapList trông giống như

scala> "abc".toList mapList (_.reverse.mkString) 
res1: List[String] = List(cba, cb, c) 

*/

Answer 2

cơ bản Bạn đã xác định những gì bạn đang tìm kiếm trong mã giả - vì vậy thật dễ dàng để thêm phương thức như vậy vào danh sách Scala bằng cách sử dụng chuyển đổi ngầm định:

object ExtendedList{ 
    implicit def List2ExtendedList[A](l:List[A])=new ExtendedList(l) 
} 
class ExtendedList[A](l:List[A]){ 
    import ExtendedList._ 
    def mapList[B](f:List[A]=>B):List[B]=l.length match { 
    case 0 => List() 
    case _ => f(l)::l.tail.mapList(f) 
    } 
} 

object Test extends Application{ 
    import ExtendedList._ 
    val test = List(5,4,3,2,1) 
    assert(List(15,10,6,3,1)==test.mapList{l=>(0/:l){_+_}}) 
} 

Đây có phải là những gì bạn đang tìm kiếm không?

Answer 3

Câu trả lời khác là đóng, nhưng bạn nên không bao giờ sử dụng List#length trừ khi thật cần thiết. Đặc biệt, nó làm cho giải pháp của mình O (n^2) khi sự cố là kế thừa O (n). Dưới đây là một phiên bản sạch-up:

implicit def addListSyntax[A](list: List[A]) = new { 
    def mapList[B](f: List[A]=>B) = { 
    // use inner function to avoid repeated conversions 
    def loop(list: List[A]): List[B] = list match { 
     case ls @ (_ :: tail) => f(ls) :: loop(tail) 
     case Nil => Nil 
    } 

    loop(list) 
    } 
} 

Và, để trả lời câu hỏi ban đầu của bạn: không có, không có cách nào để làm điều này bằng các phương pháp tiện ích tiêu chuẩn. Tôi thực sự hơi tò mò về lý do tại sao bạn sẽ muốn một cái gì đó như thế này ...