Декартово произведение траверсы в скалазе

Question

В Блог Эрика Торреборре на бумаге Суть шаблона итератора , он описывает, как декартово произведение хода также является траверсой.

Может кто-нибудьпокажи мне пример использования библиотеки scalaz , как я не могу понять.Допустим, проблема в том, что для List[Int] я хочу предоставить оба из:

1. Сумма Int элементов в списке
2. A List[String]элементы которого создаются путем добавления "Z" к строковому представлению Int s

Насколько я понимаю, я могу сделать это, используя traverse, но таким образом, чтобы толькона самом деле пересечь мою структуру один раз, в отличие от этого решения:

val xs = List(1, 2, 3, 4)
val (sum, strings)  = (xs.sum, xs map (_.toString + "Z"))

NOTE 1 - Я знаю, что есть другие способы сделать это, и что мне тоже не нужно перемещаться в этом примереи даже не обходить даже обязательно самый ясный способ ее решить.Я, однако, пытаюсь понять ход, поэтому я действительно ищу ответ на вопрос, как указано

EDIT - спасибо missingfaktor ниже за показ того, как это сделать, используя State.Я предполагаю, что я хочу знать, как я могу составить два независимых вычисления.Например;мои функции условно выглядят следующим образом:

val shape = (_ : List[Int]) map (_.toString + "Z")
val accum = (_ : List[Int]).sum

Я хочу, чтобы эти механизмы накопления независимо друг от друга, а затем выбрать, пройти ли мой List[Int]используя или или оба из них.Я представлял некоторый код, подобный следующему:

xs traverse shape //A List[String]
xs traverse accum //An Int

xs traverse (shape <x> accum) //The pair (List[String], Int)

Эрик подразумевает, что это возможно, но я не понимаю, как это сделать, т.е. я не вижу, как определить shape и * 1052.* таким образом, что они могут быть составлены, ни как их составить.

ПРИМЕЧАНИЕ 2 , что shape и accum не предназначены для буквального обозначения функций с сигнатурами, как указано выше.Это выражения, которые имеют тип, необходимый для выполнения описанных выше обходов.

Answer 1

Я добавляю свой собственный ответ, основанный на ответе Джейсона, чтобы показать различные способы обхода списка:

import org.specs2._
import scalaz.std.anyVal._, scalaz.std.list._
import scalaz._, std.tuple._
import scalaz.{Monoid, Applicative}

class TraverseSpec extends mutable.Specification {

  implicit val Sum = Monoid[Int].applicative
  implicit val Concat = Monoid[List[String]].applicative
  implicit val A: Applicative[({type λ[α] = (Int, List[String])})#λ] = Sum.product[({type λ[α]=List[String]})#λ](Concat)
  val xs = List(1, 2, 3, 4)

  "traverse - by folding the list with a Monoid" >> {
    val (sum, text) = Foldable[List].foldMap(xs)(a => (a, List(a.toString + "Z")))
    (sum, text) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with a function returning a tuple" >> {
    val (sum, text) = A.traverse(xs)(a => (a, List(a.toString + "Z")))
    (sum, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with 2 functions and 2 traversals" >> {
    val count   = (a: Int) => a
    val collect = (a: Int) => List(a.toString+"Z")

    val sum  = Sum.traverse(xs)(count)
    val text = Concat.traverse(xs)(collect)

    (sum, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
  "traverse - with 2 functions and 1 fused traversal" >> {
    val sum     = (a: Int) => a
    val collect = (a: Int) => List(a.toString+"Z")

    implicit def product[A, B, C](f: A => B): Product[A, B] = Product(f)
    case class Product[A, B](f: A => B) {
      def <#>[C](g: A => C) = (a: A) => (f(a), g(a))
    }

    val (total, text)  = A.traverse(xs)(sum <#> collect)
    (total, text.reverse) === (10, List("1Z", "2Z","3Z", "4Z"))
  }
}

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

Answer 2

Вы не видите здесь большой победы, потому что вы просто рекламируете простые моноиды в аппликативах, так что вы сливаете их вместе.

import scalaz.std.anyVal._, scalaz.std.list._, scalaz.std.string._
val Sum = Monoid[Int].applicative
val Concat = Monoid[List[String]].applicative
val A: Applicative[({type λ[α] = (Int, List[String])})#λ] = Sum.product[({type λ[α]=List[String]})#λ](Concat)

val xs = List(1, 2, 3, 4)
val (sum, text) = A.traverse(xs)(a => (a, List(a.toString + "Z")))
println(sum, text) // 10, List("1Z", "2Z", "3Z", "4Z")

Возможно, просто используйте Monoid[(Int, List[String])] для указанной проблемы:

import scalaz._, std.tuple._
val (sum1, text1) = Foldable[List].foldMap(xs)(a => (a, List(a.toString + "Z")))
println(sum1, text1) // 10, List("1Z", "2Z", "3Z", "4Z")

Вещи становятся более интересными, если один из эффектов, которые вы хотите пройти, является нетривиальным аппликативом, как State.

Answer 3

Дебашиш Гош написал хороший пост на эту тему.Основываясь на коде в этом посте:

scala> List(1, 2, 3, 4)
res87: List[Int] = List(1, 2, 3, 4)

scala> .traverse[({ type L[X] = State[Int, X] })#L, String] { cur =>
     |   state { (acc: Int) => (acc + cur, cur.toString + "Z") }
     | }
res88: scalaz.State[Int,List[String]] = scalaz.States$$anon$1@199245

scala> .apply(0)
res89: (Int, List[String]) = (10,List(1Z, 2Z, 3Z, 4Z))

Редактировать:

У вас есть две функции List[A] => B и List[A] => C, и вы хотите функцию List[A] => (B, C).Вот для чего &&&.Это не будет сливать петли, хотя.Я не могу себе представить, как можно соединить петли для такого случая.

Fwiw, код:

scala> val shape = (_ : List[Int]) map (_.toString + "Z")
       val accum = (_ : List[Int]).sum
shape: List[Int] => List[java.lang.String] = <function1>
accum: List[Int] => Int = <function1>

scala> val xs = List(1, 2, 3, 4)
xs: List[Int] = List(1, 2, 3, 4)

scala> (shape &&& accum) apply xs
res91: (List[java.lang.String], Int) = (List(1Z, 2Z, 3Z, 4Z),10)

Редактировать 2:

Если у вас есть функции A => B и A => C, вы можете объединить их в A => (B, C), используя &&&.Теперь, если B : Monoid и C : Monoid, вы можете использовать foldMap, чтобы получить List[A] => (B, C).Это сделает все за один цикл.

Код:

scala> val f: Int => Int = identity
f: Int => Int = <function1>

scala> val g: Int => List[String] = i => List(i.toString + "Z")
g: Int => List[String] = <function1>

scala> List(1, 2, 3, 4).foldMap(f &&& g)
res95: (Int, List[String]) = (10,List(1Z, 2Z, 3Z, 4Z))

Окончательное редактирование: (клянусь, я не редактирую это снова.)

Поскольку эти концепции берут свое начало в Хаскеле, я подумал, что было бы неплохо повторно опубликовать этот вопрос под тегом Хаскелл , и я это сделал. Ответ там , кажется, согласуется с тем, что я сказал в этой теме.Надеюсь, это помогает.

Answer 4

Если я правильно вас понимаю, то, что вы ищете, должно быть описано в примере ветки scala-seven: WordCount. Это также вовлекает государство. Я на мобильном телефоне, в противном случае я бы предоставил ссылку.

Вот ссылки:

• Скалаз 6
• Скалаз 7

HTH Andreas

EDIT:

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

https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Applicative.scala#L46

Так что вам нужно определить аппликативную форму для ваших двух функций shape и аккумулятора. Где мог быть смоделирован как государственный аппликатив.

Если мы посмотрим на эту строку, сформируем пример: val WordCount = StateT.stateMonad [Int] .compose ({тип λ [α] = Int}) # λ

Создает аппликатив, который «работает» (извините за плохую формулировку), в котором говорится. Обычно на ходу у вас есть только текущий элемент, ничего больше. Но если вы хотите вычислить на предыдущих вычислениях, вам нужно состояние, так что это создает аппликативное состояние, которое возвращает 1 для каждого элемента, который он проходит (см. Monoid [Int] .applicative).

Теперь, чтобы действительно что-то сделать, нам нужно взглянуть на метод atWordStart, и вам нужно определить метод, который может работать с созданным аппликативным WordCount (используя State)

Вот еще один пример из scalaz 6, который является более простым. Я думаю, что важно наблюдать за initialValue и как это делает метод transform1:

import scalaz._
import Scalaz._

object StateTraverseExample {

  type StS[x] = State[(Set[Int], Boolean), x] 

  def main(args: Array[String]): Unit = {
    println("apparently it works " + countAndMap(Vector.range(0, 20)))
  }

  def transform1(i: Int, l: Set[Int], result: Boolean): (Set[Int],Boolean) = {
    if (result || (l contains i))
      (l, true)
    else
      (l + i, false)
   }

  def countAndMap(l: Vector[Int]): (Set[Int],Boolean) = {
    val initialValue=(Set.empty[Int], false)

    val counts = l.traverse[StS, Unit] { i => 
      state { case (set, result) => (transform1(i,set,result), println(i))   }
    } ~> initialValue
    counts
  }
}

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