Отображение подсписков в Scala - PullRequest
Новая
       30

Отображение подсписков в Scala

6 голосов
/ 21 мая 2009

Я знаю, что функция карты берет каждый элемент списка (последовательность) и применяет к нему функцию. Рекурсивно (и без учета условий завершения и т. Д.) 

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

Я ищу функцию, которая делает что-то вроде 

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

Таким образом, 'mapper', где функция отображения вызывается для подсписков, а не для отдельных элементов. В терминах LISP я ищу список карт, а не карту. Существует ли что-то подобное, или я должен свернуть свой собственный (или использовать рекурсию)?

В качестве альтернативы я бы взял функцию, которая принимает в качестве входных данных последовательность и возвращает последовательность промежуточных подпоследовательностей, т.е. 

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

Ответы [ 3 ]

5 голосов
/ 21 мая 2009

/ * Этот подход определяет mapList в терминах другого полезного метода, называемого tails. Как и Даниэль, я добавлю это в неявное расширение List, но это чисто вопрос вкуса * / 

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

/ * Вот метод с именем tails, который возвращает каждый возможный хвост в списке. Он хвостовой рекурсии, поэтому он не будет взорван в больших списках. Обратите внимание, что он немного отличается от одноименной функции Haskell. Версия на Haskell всегда добавляет пустой список к результату * / 

  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
  }

/ * Вот так выглядит использование хвостов 

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

* /

/ * Теперь мы можем определить mapList на основе хвостов * / 

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

/ * Вот как выглядит mapList 

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

* /

2 голосов
/ 21 мая 2009

Вы в основном определили, что вы ищете в псевдокоде - так что легко добавить такой метод в список Scala, используя неявные преобразования: 

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){_+_}})
}

Это то, что вы ищете?

1 голос
/ 21 мая 2009

Другой ответ близок, но вы не должны никогда использовать List#length, если в этом нет крайней необходимости. В частности, это делает его решение O (n ^ 2) , когда проблема неотвратимо O (n) . Вот очищенная версия: 

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)
  }
}

И, чтобы ответить на ваш оригинальный вопрос: нет, это невозможно сделать с помощью стандартных служебных методов. Мне на самом деле немного любопытно, почему вы хотите что-то подобное ...

...