As HLists nada mais são do que uma maneira complicada de escrever tuplas?

144

Estou realmente interessado em descobrir onde estão as diferenças e, de maneira mais geral, identificar casos de uso canônicos em que as HLists não podem ser usadas (ou melhor, não produzem nenhum benefício em relação às listas regulares).

(Estou ciente de que existem 22 (acredito)) TupleNem Scala, enquanto um só precisa de uma única HList, mas esse não é o tipo de diferença conceitual em que estou interessado.)

Marquei algumas perguntas no texto abaixo. Talvez não seja realmente necessário respondê-las, elas têm mais a intenção de apontar coisas que não são claras para mim e orientar a discussão em determinadas direções.

Motivação

Recentemente, vi algumas respostas no SO, nas quais as pessoas sugeriram o uso de HLists (por exemplo, conforme fornecido por Shapeless ), incluindo uma resposta excluída para esta pergunta . Isso deu origem a essa discussão , que por sua vez provocou essa questão.

Introdução

Parece-me que hlists são úteis apenas quando você conhece estaticamente o número de elementos e seus tipos precisos. O número não é realmente crucial, mas parece improvável que você precise gerar uma lista com elementos de tipos variados, mas estaticamente precisamente conhecidos, mas que não saiba estaticamente o número deles. Pergunta 1: Você poderia escrever um exemplo como, por exemplo, em um loop? Minha intuição é que ter uma lista estaticamente precisa com um número estaticamente desconhecido de elementos arbitrários (arbitrário em relação a uma determinada hierarquia de classes) simplesmente não é compatível.

HLists vs. Tuplas

Se isso for verdade, ou seja, você sabe estaticamente o número e o tipo - Pergunta 2: por que não usar apenas uma n-tupla? Claro, você pode tipicamente mapear e dobrar uma HList (que você também pode, mas não tipicamente, fazer sobre uma tupla com a ajuda de productIterator), mas como o número e o tipo dos elementos são estaticamente conhecidos, você provavelmente pode acessar os elementos da tupla diretamente e executar as operações.

Por outro lado, se a função que fvocê mapeia sobre uma lista é tão genérica que aceita todos os elementos - Pergunta 3: por que não usá-la productIterator.map? Ok, uma diferença interessante poderia vir da sobrecarga de método: se tivéssemos várias sobrecarregadas f, ter as informações de tipo mais fortes fornecidas pela hlist (em contraste com o productIterator) poderia permitir ao compilador escolher uma mais específica f. No entanto, não tenho certeza se isso realmente funcionaria no Scala, pois métodos e funções não são os mesmos.

HLists e entrada do usuário

Com base na mesma suposição, a saber, que você precisa conhecer o número e os tipos dos elementos estaticamente - Questão 4: as listas podem ser usadas em situações em que os elementos dependem de qualquer tipo de interação do usuário? Por exemplo, imagine preencher uma hlist com elementos dentro de um loop; os elementos são lidos de algum lugar (interface do usuário, arquivo de configuração, interação do ator, rede) até que uma determinada condição seja mantida. Qual seria o tipo da lista? Semelhante para uma especificação de interface getElements: [...] HList que deve funcionar com listas de tamanho estaticamente desconhecido e que permite que o componente A em um sistema obtenha essa lista de elementos arbitrários do componente B.

Malte Schwerhoff
fonte

Respostas:

144

Abordando as perguntas de um a três: um dos principais aplicativos para HListsabstrair a aridade. O Arity é normalmente conhecido estaticamente em qualquer site de uso de uma abstração, mas varia de site para site. Tomemos isso, a partir dos exemplos disformes ,

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)

Sem usar HLists(ou algo equivalente) para abstrair a aridade dos argumentos da tupla flatten, seria impossível ter uma única implementação que pudesse aceitar argumentos dessas duas formas muito diferentes e transformá-los de uma maneira segura.

É provável que a capacidade de abstrair a aridade seja interessante em qualquer lugar em que as aridades fixas estejam envolvidas: assim como as tuplas, como acima, que incluem listas de parâmetros de método / função e classes de caso. Veja aqui exemplos de como podemos abstrair a aridade de classes de caso arbitrárias para obter instâncias de classe de tipo quase automaticamente,

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

Não há iteração de tempo de execução aqui, mas há duplicação que o uso de HLists(ou estruturas equivalentes) pode eliminar. Obviamente, se sua tolerância a clichês repetitivos for alta, você poderá obter o mesmo resultado escrevendo várias implementações para cada forma que lhe interessa.

Na pergunta três, você pergunta "... se a função f que você mapeia sobre uma lista é tão genérica que aceita todos os elementos ... por que não usá-la através do productIterator.map?". Se a função que você mapeia sobre uma HList realmente tiver a forma Any => T, o mapeamento productIteratorserá útil perfeitamente. Mas as funções do formulário Any => Tgeralmente não são tão interessantes (pelo menos, não são, a menos que digitem elenco internamente). shapeless fornece uma forma de valor da função polimórfica que permite ao compilador selecionar casos específicos de tipo exatamente da maneira que você duvida. Por exemplo,

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

Com relação à sua pergunta quatro, sobre a entrada do usuário, há dois casos a serem considerados. O primeiro são situações em que podemos estabelecer dinamicamente um contexto que garante a obtenção de uma condição estática conhecida. Nesses tipos de cenários, é perfeitamente possível aplicar técnicas disformes, mas claramente com a condição de que, se a condição estática não for obtida no tempo de execução, precisamos seguir um caminho alternativo. Sem surpresa, isso significa que os métodos sensíveis a condições dinâmicas precisam produzir resultados opcionais. Aqui está um exemplo usando 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]

O tipo de lnão captura o comprimento da lista ou os tipos precisos de seus elementos. No entanto, se esperamos que ele tenha uma forma específica (ou seja, se precisar estar em conformidade com algum esquema fixo conhecido), podemos tentar estabelecer esse fato e agir em conformidade,

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

Existem outras situações em que talvez não nos importemos com o tamanho real de uma determinada lista, exceto que ele tem o mesmo tamanho de alguma outra lista. Novamente, isso é algo que suporta a forma, totalmente estaticamente, e também em um contexto estático / dinâmico misto como acima. Veja aqui um exemplo estendido.

É verdade, como você observa, que todos esses mecanismos exigem que as informações do tipo estático estejam disponíveis, pelo menos condicionalmente, e isso parece excluir que essas técnicas sejam utilizáveis ​​em um ambiente completamente dinâmico, totalmente controlado por dados não digitados fornecidos externamente. Mas com o advento do suporte à compilação de tempo de execução como um componente do reflexo do Scala na versão 2.10, mesmo isso não é mais um obstáculo insuperável ... podemos usar a compilação de tempo de execução para fornecer uma forma de teste leve e ter nossa tipagem estática executada em tempo de execução em resposta a dados dinâmicos: trecho do anterior abaixo ... siga o link para o exemplo completo,

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

Tenho certeza que o @PLT_Borat terá algo a dizer sobre isso, dados os comentários prudentes dele sobre as linguagens de programação dependentes ;-)

Miles Sabin
fonte
2
Estou um pouco intrigado com a última parte da sua resposta - mas também muito intrigado! Obrigado pela sua grande resposta e as muitas referências, parece que eu tenho um monte de leitura para fazer :-)
Malte Schwerhoff
1
Abstrair sobre aridade é extremamente útil. Infelizmente, o ScalaMock sofre uma duplicação considerável porque as várias FunctionNcaracterísticas não sabem abstrair a aridade: github.com/paulbutcher/ScalaMock/blob/develop/core/src/main/… github.com/paulbutcher/ScalaMock/blob / desenvolver / core / src / main / ... Infelizmente eu não estou ciente de qualquer maneira que eu possa usar Shapeless para evitar isso, já que eu preciso para lidar com "real" FunctionNs
Paul Butcher
1
Eu criei um exemplo (bastante artificial) - ideone.com/sxIw1 -, que está na linha da primeira pergunta. Isso poderia se beneficiar das listas, talvez em combinação com "a digitação estática realizada em tempo de execução em resposta a dados dinâmicos"? (Ainda não tenho certeza que o último é exatamente sobre)
Malte Schwerhoff
18

Só para esclarecer, uma HList nada mais é do que uma pilha de Tuple2açúcar ligeiramente diferente por cima.

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

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

Portanto, sua pergunta é essencialmente sobre as diferenças entre o uso de tuplas aninhadas e de tuplas planas, mas as duas são isomórficas; portanto, no final, realmente não há diferença, exceto a conveniência de que funções da biblioteca podem ser usadas e qual notação pode ser usada.

Dan Burton
fonte
as tuplas podem ser mapeadas para hlists e voltar de qualquer maneira, para que haja um isomorfismo claro.
precisa
10

Há muitas coisas que você não pode fazer (bem) com tuplas:

  • escrever uma função genérica de prefixar / acrescentar
  • escreva uma função reversa
  • escrever uma função concat
  • ...

Você pode fazer tudo isso com tuplas, é claro, mas não no caso geral. Portanto, usar HLists torna seu código mais SECO.

Kim Stebel
fonte
8

Eu posso explicar isso em linguagem super simples:

A nomeação de tupla versus lista não é significativa. HLists podem ser nomeadas como HTuples. A diferença é que, no Scala + Haskell, você pode fazer isso com uma tupla (usando a sintaxe do Scala):

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

para obter uma tupla de entrada com exatamente dois elementos de qualquer tipo, anexar um terceiro elemento e retornar uma tupla totalmente digitada com exatamente três elementos. Mas, embora seja genérico sobre os tipos, ele precisa especificar explicitamente os comprimentos de entrada / saída.

O que um HList do estilo Haskell permite fazer é tornar esse genérico excedente, para que você possa anexar a qualquer comprimento da tupla / lista e recuperar uma lista / tupla totalmente digitada estaticamente. Esse benefício também se aplica a coleções de tipo homogêneo, nas quais você pode anexar um int a uma lista de exatamente n ints e recuperar uma lista que é digitada estaticamente para ter exatamente (n + 1) ints sem especificar explicitamente n.

argila
fonte