Mappage de sous-listes dans Scala

Question

Je sais que la fonction map prend chaque élément d'une liste (une séquence) et lui applique une fonction. Récursive (et sans respect des conditions de licenciement, etc.)

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

Je cherche une fonction qui fait quelque chose comme

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

donc un « cartographe » où la fonction de mappage est appelée sur les sous-listes et non éléments individuels. En termes de lisp, je cherche un mapliste, par opposition à un mapcar. Est-ce que quelque chose comme ça existe, ou dois-je rouler le mien (ou utiliser la récursivité)?

Sinon, je prendrais une fonction qui prend en entrée une séquence et retourne une séquence de séquences mi-bout, à savoir

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

Answer 1

/* Cette approche définit mapList en termes d'une autre méthode utile appelée queues. Comme Daniel, je vais le mettre dans une extension implicite à la liste, mais c'est purement une question de goût */

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

/* Voici une méthode appelée queue qui retourne chaque queue possible dans la liste. Il est récursif à la queue, donc il ne va pas exploser sur de grandes listes. Notez qu'il diffère légèrement d'une fonction Haskell du même nom. La version Haskell ajoute toujours une liste vide sur le résultat */

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 
    } 

/* Ceci est ce que l'utilisation des queues ressemble

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

*/

/* Maintenant, nous pouvons définir maplist sur la base des queues */

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

/* voici ce que l'utilisation maplist ressemble

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

*/

Answer 2

Vous avez essentiellement défini ce que vous cherchez dans pseudocode - il est donc facile d'ajouter une telle méthode à une liste Scala en utilisant les conversions implicites:

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

est-ce que vous cherchez?

Answer 3

L'autre réponse est proche, mais vous devez jamais utiliser List#length sauf si absolument nécessaire. En particulier, il fait sa solution O (n^2) lorsque le problème est inhérent O (n). Voici une version assainis:

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

Et, pour répondre à votre question initiale: non, il n'y a aucun moyen de le faire en utilisant des méthodes utilitaires standard. Je suis en fait un peu curieux de savoir pourquoi vous voudriez quelque chose comme ça ...