Sind HLists nichts anderes als eine verschlungene Art, Tupel zu schreiben?

144

Ich bin wirklich daran interessiert herauszufinden, wo die Unterschiede liegen, und allgemeiner, kanonische Anwendungsfälle zu identifizieren, in denen HLists nicht verwendet werden können (oder vielmehr keine Vorteile gegenüber regulären Listen bieten).

(Mir ist bewusst, dass es TupleNin Scala 22 (glaube ich) gibt , während man nur eine einzige HList benötigt, aber das ist nicht der konzeptionelle Unterschied, an dem ich interessiert bin.)

Ich habe im folgenden Text einige Fragen markiert. Es ist möglicherweise nicht notwendig, sie zu beantworten, sie sollen eher auf Dinge hinweisen, die mir unklar sind, und die Diskussion in bestimmte Richtungen leiten.

Motivation

Ich habe kürzlich einige Antworten auf SO gesehen, in denen Leute vorgeschlagen haben, HLists zu verwenden (zum Beispiel, wie von Shapeless bereitgestellt ), einschließlich einer gelöschten Antwort auf diese Frage . Es entstand diese Diskussion , die wiederum diese Frage auslöste.

Intro

Es scheint mir, dass Listen nur dann nützlich sind, wenn Sie die Anzahl der Elemente und ihre genauen Typen statisch kennen. Die Anzahl ist eigentlich nicht entscheidend, aber es ist unwahrscheinlich, dass Sie jemals eine Liste mit Elementen unterschiedlicher, aber statisch genau bekannter Typen erstellen müssen, aber dass Sie deren Anzahl statisch nicht kennen. Frage 1: Könnten Sie ein solches Beispiel überhaupt schreiben, z. B. in einer Schleife? Meine Intuition ist, dass eine statisch genaue Liste mit einer statisch unbekannten Anzahl beliebiger Elemente (willkürlich relativ zu einer bestimmten Klassenhierarchie) einfach nicht kompatibel ist.

HLists vs. Tuples

Wenn dies zutrifft, dh Sie kennen statisch Nummer und Typ - Frage 2: Warum nicht einfach ein n-Tupel verwenden? Sicher, Sie können eine HList typsicher zuordnen und falten (was Sie auch, aber nicht typsicher, mit Hilfe von über ein Tupel tun können productIterator), aber da Anzahl und Typ der Elemente statisch bekannt sind, können Sie wahrscheinlich einfach auf die Tupelelemente zugreifen direkt und führen Sie die Operationen.

Auf der anderen Seite, wenn die Funktion, die fSie einer hlist zuordnen, so allgemein ist, dass sie alle Elemente akzeptiert - Frage 3: Warum nicht über verwenden productIterator.map? Ok, ein interessanter Unterschied könnte sich aus dem Überladen von Methoden ergeben: Wenn wir mehrere überladene fMethoden hätten, könnte der Compiler aufgrund der stärkeren Typinformationen, die von der hlist bereitgestellt werden (im Gegensatz zum productIterator), eine spezifischere auswählen f. Ich bin mir jedoch nicht sicher, ob dies in Scala tatsächlich funktionieren würde, da Methoden und Funktionen nicht identisch sind.

HLists und Benutzereingaben

Aufbauend auf der gleichen Annahme, dass Sie Anzahl und Typ der Elemente statisch kennen müssen - Frage 4: Können Listen in Situationen verwendet werden, in denen die Elemente von irgendeiner Art von Benutzerinteraktion abhängen? Stellen Sie sich beispielsweise vor, Sie füllen eine hlist mit Elementen innerhalb einer Schleife. Die Elemente werden von irgendwoher gelesen (Benutzeroberfläche, Konfigurationsdatei, Interaktion mit dem Akteur, Netzwerk), bis eine bestimmte Bedingung erfüllt ist. Was wäre der Typ der hlist? Ähnliches gilt für eine Schnittstellenspezifikation getElements: HList [...], die mit Listen statisch unbekannter Länge arbeiten soll und die es Komponente A in einem System ermöglicht, eine solche Liste beliebiger Elemente von Komponente B abzurufen.

Malte Schwerhoff
quelle

Antworten:

144

Beantwortung der Fragen eins bis drei: Eine der Hauptanwendungen HListsist das Abstrahieren über Arität. Arity ist normalerweise statisch an jedem Verwendungsort einer Abstraktion bekannt, variiert jedoch von Ort zu Ort. Nehmen Sie dies aus den Beispielen von Shapeless :

def flatten[T <: Product, L <: HList](t : T)
  (implicit hl : HListerAux[T, L], flatten : Flatten[L]) : flatten.Out =
    flatten(hl(t))

val t1 = (1, ((2, 3), 4))
val f1 = flatten(t1)     // Inferred type is Int :: Int :: Int :: Int :: HNil
val l1 = f1.toList       // Inferred type is List[Int]

val t2 = (23, ((true, 2.0, "foo"), "bar"), (13, false))
val f2 = flatten(t2)
val t2b = f2.tupled
// Inferred type of t2b is (Int, Boolean, Double, String, String, Int, Boolean)

Ohne die Verwendung HLists(oder etwas Äquivalentes) zur Abstraktion über die Arität der Tupelargumente flattenwäre es unmöglich, eine einzige Implementierung zu haben, die Argumente dieser beiden sehr unterschiedlichen Formen akzeptieren und sie auf typsichere Weise transformieren könnte.

Die Fähigkeit, über Arität zu abstrahieren, ist wahrscheinlich überall dort von Interesse, wo feste Aritäten beteiligt sind: sowie Tupel wie oben, die Methoden- / Funktionsparameterlisten und Fallklassen enthalten. Sehen Sie hier für Beispiele dafür , wie wir könnten abstrakt über die arity beliebiger Fallklassen Typ Klasseninstanzen zu erhalten fast automatisch,

// A pair of arbitrary case classes
case class Foo(i : Int, s : String)
case class Bar(b : Boolean, s : String, d : Double)

// Publish their `HListIso`'s
implicit def fooIso = Iso.hlist(Foo.apply _, Foo.unapply _)
implicit def barIso = Iso.hlist(Bar.apply _, Bar.unapply _)

// And now they're monoids ...

implicitly[Monoid[Foo]]
val f = Foo(13, "foo") |+| Foo(23, "bar")
assert(f == Foo(36, "foobar"))

implicitly[Monoid[Bar]]
val b = Bar(true, "foo", 1.0) |+| Bar(false, "bar", 3.0)
assert(b == Bar(true, "foobar", 4.0))

Es gibt keine Laufzeit Iteration hier, aber es gibt Überschneidungen , die die Verwendung von HLists(oder äquivalenten Strukturen) beseitigen. Wenn Ihre Toleranz für sich wiederholende Kesselplatten hoch ist, können Sie natürlich das gleiche Ergebnis erzielen, indem Sie mehrere Implementierungen für jede Form schreiben, die Sie interessiert.

In Frage drei fragen Sie: "... wenn die Funktion, die Sie einer hlist zuordnen, so allgemein ist, dass sie alle Elemente akzeptiert ... warum nicht über productIterator.map verwenden?". Wenn die Funktion Sie eine hList wirklich von der Form der Karte über Any => Tdann Abbilden über productIteratorwerden Sie sehr gut dienen. Aber Funktionen des Formulars Any => Tsind normalerweise nicht so interessant (zumindest nicht, wenn sie nicht intern cast eingeben). Shapeless bietet eine Form von polymorphem Funktionswert, mit dem der Compiler typspezifische Fälle genau so auswählen kann, wie Sie Zweifel haben. Zum Beispiel,

// size is a function from values of arbitrary type to a 'size' which is
// defined via type specific cases
object size extends Poly1 {
  implicit def default[T] = at[T](t => 1)
  implicit def caseString = at[String](_.length)
  implicit def caseList[T] = at[List[T]](_.length)
}

scala> val l = 23 :: "foo" :: List('a', 'b') :: true :: HNil
l: Int :: String :: List[Char] :: Boolean :: HNil =
  23 :: foo :: List(a, b) :: true :: HNil

scala> (l map size).toList
res1: List[Int] = List(1, 3, 2, 1)

In Bezug auf Ihre vierte Frage zur Benutzereingabe sind zwei Fälle zu berücksichtigen. Das erste sind Situationen, in denen wir dynamisch einen Kontext herstellen können, der garantiert, dass ein bekannter statischer Zustand vorliegt. In solchen Szenarien ist es durchaus möglich, formlose Techniken anzuwenden, aber mit der Maßgabe, dass wir einen alternativen Weg einschlagen müssen, wenn die statische Bedingung zur Laufzeit nicht eintritt. Es ist nicht überraschend, dass Methoden, die empfindlich auf dynamische Bedingungen reagieren, optionale Ergebnisse liefern müssen. Hier ist ein Beispiel mit HLists,

trait Fruit
case class Apple() extends Fruit
case class Pear() extends Fruit

type FFFF = Fruit :: Fruit :: Fruit :: Fruit :: HNil
type APAP = Apple :: Pear :: Apple :: Pear :: HNil

val a : Apple = Apple()
val p : Pear = Pear()

val l = List(a, p, a, p) // Inferred type is List[Fruit]

Der Typ von lerfasst nicht die Länge der Liste oder die genauen Typen ihrer Elemente. Wenn wir jedoch erwarten, dass es eine bestimmte Form hat (dh wenn es einem bekannten, festen Schema entsprechen sollte), können wir versuchen, diese Tatsache festzustellen und entsprechend zu handeln.

scala> import Traversables._
import Traversables._

scala> val apap = l.toHList[Apple :: Pear :: Apple :: Pear :: HNil]
res0: Option[Apple :: Pear :: Apple :: Pear :: HNil] =
  Some(Apple() :: Pear() :: Apple() :: Pear() :: HNil)

scala> apap.map(_.tail.head)
res1: Option[Pear] = Some(Pear())

Es gibt andere Situationen, in denen uns die tatsächliche Länge einer bestimmten Liste möglicherweise nicht wichtig ist, außer dass sie dieselbe Länge wie eine andere Liste hat. Auch dies ist etwas, das formlos unterstützt, sowohl vollständig statisch als auch in einem gemischten statischen / dynamischen Kontext wie oben. Sehen Sie hier für ein längeres Beispiel.

Wie Sie feststellen, müssen für alle diese Mechanismen zumindest bedingt statische Typinformationen verfügbar sein, und dies scheint zu verhindern, dass diese Techniken in einer vollständig dynamischen Umgebung verwendet werden können, die vollständig von extern bereitgestellten nicht typisierten Daten gesteuert wird. Mit dem Aufkommen der Unterstützung für die Laufzeitkompilierung als Bestandteil der Scala-Reflexion in 2.10 ist auch dies kein unüberwindbares Hindernis mehr. Wir können die Laufzeitkompilierung verwenden, um eine Form der einfachen Bereitstellung bereitzustellen und unsere statische Typisierung zur Laufzeit durchführen zu lassen als Antwort auf dynamische Daten: Auszug aus dem vorhergehenden unten ... folgen Sie dem Link für das vollständige Beispiel,

val t1 : (Any, Any) = (23, "foo") // Specific element types erased
val t2 : (Any, Any) = (true, 2.0) // Specific element types erased

// Type class instances selected on static type at runtime!
val c1 = stagedConsumeTuple(t1) // Uses intString instance
assert(c1 == "23foo")

val c2 = stagedConsumeTuple(t2) // Uses booleanDouble instance
assert(c2 == "+2.0")

Ich bin mir sicher, dass @PLT_Borat etwas dazu zu sagen haben wird, angesichts seiner weisen Kommentare zu abhängig getippten Programmiersprachen ;-)

Miles Sabin
quelle
2
Der letzte Teil Ihrer Antwort verwirrt mich ein wenig - aber auch sehr fasziniert! Vielen Dank für Ihre tolle Antwort und die vielen Referenzen, sieht so aus, als hätte ich viel zu lesen :-)
Malte Schwerhoff
1
Das Abstrahieren über Arität ist äußerst nützlich. ScalaMock leidet leider unter erheblichen Überschneidungen, da die verschiedenen FunctionNMerkmale nicht über Arity abstrahieren können: github.com/paulbutcher/ScalaMock/blob/develop/core/src/main/… github.com/paulbutcher/ScalaMock/blob / Develop / Core / Src / Main /… Leider ist mir keine Möglichkeit bewusst, wie ich Shapeless verwenden kann, um dies zu vermeiden, da ich mich mit "echten" FunctionNs befassen muss
Paul Butcher
1
Ich habe mir ein (ziemlich künstliches) Beispiel ausgedacht - ideone.com/sxIw1 -, das der ersten Frage entspricht. Könnte dies von Listen profitieren, möglicherweise in Kombination mit "statischer Typisierung zur Laufzeit als Reaktion auf dynamische Daten"? (Ich bin mir immer noch nicht sicher, worum es bei letzterem genau geht)
Malte Schwerhoff
17

Um ganz klar zu sein, eine HList ist im Wesentlichen nichts anderes als ein Stapel Tuple2mit etwas anderem Zucker.

def hcons[A,B](head : A, tail : B) = (a,b)
def hnil = Unit

hcons("foo", hcons(3, hnil)) : (String, (Int, Unit))

Bei Ihrer Frage geht es also im Wesentlichen um die Unterschiede zwischen der Verwendung verschachtelter Tupel und flachen Tupeln, aber die beiden sind isomorph, sodass es am Ende wirklich keinen Unterschied gibt, außer der Bequemlichkeit, welche Bibliotheksfunktionen verwendet werden können und welche Notation verwendet werden kann.

Dan Burton
quelle
Tupel können ohnehin auf Listen und zurück abgebildet werden, sodass ein klarer Isomorphismus vorliegt.
Erik Kaplun
10

Es gibt viele Dinge, die man mit Tupeln nicht (gut) machen kann:

  • Schreiben Sie eine generische Funktion zum Voranstellen / Anhängen
  • schreibe eine umgekehrte Funktion
  • Schreiben Sie eine Concat-Funktion
  • ...

Sie können das alles natürlich mit Tupeln machen, aber im allgemeinen Fall nicht. Wenn Sie also HLists verwenden, wird Ihr Code trockener.

Kim Stebel
quelle
8

Ich kann das in super einfacher Sprache erklären:

Die Benennung von Tupel und Liste ist nicht signifikant. HLists könnten als HTuples bezeichnet werden. Der Unterschied besteht darin, dass Sie dies in Scala + Haskell mit einem Tupel (mithilfe der Scala-Syntax) tun können:

def append2[A,B,C](in: (A,B), v: C) : (A,B,C) = (in._1, in._2, v)

Um ein Eingabetupel mit genau zwei Elementen eines beliebigen Typs zu verwenden, fügen Sie ein drittes Element hinzu und geben Sie ein vollständig typisiertes Tupel mit genau drei Elementen zurück. Dies ist zwar völlig generisch gegenüber Typen, muss jedoch die Eingabe- / Ausgabelängen explizit angeben.

Mit einer HList im Haskell-Stil können Sie diese generische Überlänge festlegen, sodass Sie an jede Länge von Tupel / Liste anhängen und ein vollständig statisch typisiertes Tupel / eine vollständig statisch typisierte Liste zurückerhalten können. Dieser Vorteil gilt auch für homogen typisierte Sammlungen, bei denen Sie ein int an eine Liste mit genau n Ints anhängen und eine statisch typisierte Liste mit genau (n + 1) Ints zurückerhalten können, ohne n explizit anzugeben.

Lehm
quelle