TreeLiteralConvertible

Evolution Discussion
1

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating an array, but a tree – a more general structure of which arrays are only a special case. Given the well-deserved and growing reputation of Swift, one would hope that in this instance the compiler would be able to default to something like a:

enum Tree<Value> {
  case Leaf(Value)
  case Branches([Tree])
}

extension Tree : ArrayLiteralConvertible {
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
}

For this to work in the playground, however, we must manually lift the values into the world of trees first. And to make that chore in turn easier on the eye we can introduce a:

prefix operator ◊ {} // looks a bit like a leaf (us/uk kbd: ⎇⇧V)
prefix func ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

The point here is that if adding such a fundamental type to the Standard Library would not be a priority at present, it is not the end of the world since we can easily enough write it ourselves… What we cannot do ourselves, however, is to get rid of the need for that operator in the common scenario of initialising with literal values. For this we need a literal-convertible protocol requiring two initialisers:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

And, whilst we are at it, we could also get rid of the need for that operator in the case of nested associative arrays (again, you can try this in the playground):

enum DictionaryTree<Key, Value> {
  case Leaf(Value)
  case Branches([(Key, DictionaryTree)])
}

extension DictionaryTree : DictionaryLiteralConvertible {
  init(dictionaryLiteral pairs: (Key, DictionaryTree)...) {
    self = .Branches(pairs)
  }
}

prefix func ◊ <Key, Value> (leaf: Value) -> DictionaryTree<Key, Value> { return .Leaf(leaf) }

let map: DictionaryTree<String,Int> = [
  "A" : [:],
  "B" : [
    "Ba" : ◊0,
    "Bb" : ◊0,
    "Bc" : [
      "Bc1" : ◊0,
      "Bc2" : ◊0,
      "Bc3" : ◊0
    ]
  ]
]

… by introducing an analogous protocol:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Please note: I do understand that fleshing out these structures (along with all the juicy methods, operators and lazy alternatives) may not currently be a priority for Swift. The two literal-convertible protocols however, may be a much less daunting task, which would open to us some very useful programming idioms…

milos

2

I think a better solution than just adding a TreeLiteral (and the accompanying TreeLiteralConvertible protocol) would be to allow user-defined literal types using regex (or something similar). This would not only allow for tremendous flexibility, but it’d remove some compiler magic as well.

There’d have to be some rules regarding overlapping definitions… The simplest I can think of is make it an error to not do type annotation when there’s more than one way to parse a literal, but I’m not sure that’s necessarily the best.

- Dave Sweeris

···

On Apr 14, 2016, at 11:27 AM, Milos Rankovic via swift-evolution <swift-evolution@swift.org> wrote:

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating an array, but a tree – a more general structure of which arrays are only a special case. Given the well-deserved and growing reputation of Swift, one would hope that in this instance the compiler would be able to default to something like a:

enum Tree<Value> {
  case Leaf(Value)
  case Branches([Tree])
}

extension Tree : ArrayLiteralConvertible {
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
}

For this to work in the playground, however, we must manually lift the values into the world of trees first. And to make that chore in turn easier on the eye we can introduce a:

prefix operator ◊ {} // looks a bit like a leaf (us/uk kbd: ⎇⇧V)
prefix func ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

The point here is that if adding such a fundamental type to the Standard Library would not be a priority at present, it is not the end of the world since we can easily enough write it ourselves… What we cannot do ourselves, however, is to get rid of the need for that operator in the common scenario of initialising with literal values. For this we need a literal-convertible protocol requiring two initialisers:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

And, whilst we are at it, we could also get rid of the need for that operator in the case of nested associative arrays (again, you can try this in the playground):

enum DictionaryTree<Key, Value> {
  case Leaf(Value)
  case Branches([(Key, DictionaryTree)])
}

extension DictionaryTree : DictionaryLiteralConvertible {
  init(dictionaryLiteral pairs: (Key, DictionaryTree)...) {
    self = .Branches(pairs)
  }
}

prefix func ◊ <Key, Value> (leaf: Value) -> DictionaryTree<Key, Value> { return .Leaf(leaf) }

let map: DictionaryTree<String,Int> = [
  "A" : [:],
  "B" : [
    "Ba" : ◊0,
    "Bb" : ◊0,
    "Bc" : [
      "Bc1" : ◊0,
      "Bc2" : ◊0,
      "Bc3" : ◊0
    ]
  ]
]

… by introducing an analogous protocol:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Please note: I do understand that fleshing out these structures (along with all the juicy methods, operators and lazy alternatives) may not currently be a priority for Swift. The two literal-convertible protocols however, may be a much less daunting task, which would open to us some very useful programming idioms…

milos
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

3

Well, actually we can compile :

var zz : [Any] = [[Int](), 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

- is empty array of unknown type, I think this is why you can't compile.

We need good language tools to process such kind of array, I agree with you.

As for your proposal.. I have no idea if this all is used often and can make our life easier. Probably some other can provide us with opinion.

···

On 14.04.2016 19:27, Milos Rankovic via swift-evolution wrote:

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating
an array, but a tree – a more general structure of which arrays are only a
special case. Given the well-deserved and growing reputation of Swift, one
would hope that in this instance the compiler would be able to default to
something like a:

enum Tree<Value> {
case Leaf(Value)
case Branches([Tree])
}

extensionTree : ArrayLiteralConvertible {
init(arrayLiteral elements: Tree...) {
self = .Branches(elements)
}

For this to work in the playground, however, we must manually lift the
values into the world of trees first. And to make that chore in turn easier
on the eye we can introduce a:

prefixoperator ◊ {} // looks a bit like a leaf (us/uk kbd: *⎇⇧*V)
prefixfunc ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

The point here is that if adding such a fundamental type to the Standard
Library would not be a priority at present, it is not the end of the world
since we can easily enough write it ourselves… What we cannot do ourselves,
however, is to get rid of the need for that operator in the common scenario
of initialising with literal values. For this we need a literal-convertible
protocol requiring *two* initialisers:

protocolTreeLiteralConvertible {
associatedtypeLeafValue
init(literal: Self.LeafValue...)
init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

And, whilst we are at it, we could also get rid of the need for that
operator in the case of nested associative arrays (again, you can try this
in the playground):

enumDictionaryTree<Key, Value> {
case Leaf(Value)
case Branches([(Key, DictionaryTree)])
}

extensionDictionaryTree : DictionaryLiteralConvertible {
init(dictionaryLiteral pairs: (Key, DictionaryTree)...) {
self = .Branches(pairs)
}

prefixfunc ◊ <Key, Value> (leaf: Value) -> DictionaryTree<Key, Value> {
return .Leaf(leaf) }

let map: DictionaryTree<String,Int> = [
"A" : [:],
"B" : [
"Ba" : ◊0,
"Bb" : ◊0,
"Bc" : [
"Bc1" : ◊0,
"Bc2" : ◊0,
"Bc3" : ◊0
]

… by introducing an analogous protocol:

protocolDictionaryTreeLiteralConvertible {
associatedtypeKey
associatedtypeLeafValue
init(literal: Self.LeafValue...)
init(literal: (Key, Self)...)
}

Please note: I do understand that fleshing out these structures (along with
all the juicy methods, operators and lazy alternatives) may not currently
be a priority for Swift. The two literal-convertible protocols however, may
be a much less daunting task, which would open to us some very useful
programming idioms…

milos

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

4

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating an array, but a tree – a more general structure of which arrays are only a special case. Given the well-deserved and growing reputation of Swift, one would hope that in this instance the compiler would be able to default to something like a:

Actually this error can be simplified to

_ =

As the compiler says, the expression is ambiguous. Without an element type, the array literal cannot be used to create an array.

On the other hand:

_ = [[1]]

is fine - the system assumes the literal your literal was defining an array of int, so the outer type is Array<Array<Int>>

For this to work in the playground, however, we must manually lift the values into the world of trees first. And to make that chore in turn easier on the eye we can introduce a:

prefix operator ◊ {} // looks a bit like a leaf (us/uk kbd: ⎇⇧V)
prefix func ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

Yes, because there is no way to have one type be cast implicitly into another type except for the cases the compiler supports via Optional or the various LiteralConvertible protocols/initializers.

So as other point out, if you actually defined a Integer-only tree, you could define that a .leaf was created from integer literals. Then this works without your wrapping operator.

The point here is that if adding such a fundamental type to the Standard Library would not be a priority at present, it is not the end of the world since we can easily enough write it ourselves… What we cannot do ourselves, however, is to get rid of the need for that operator in the common scenario of initialising with literal values. For this we need a literal-convertible protocol requiring two initialisers:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

If my tree is of Pear objects, there is no “Pear” literal in the language. So I don’t think you are asking for tree literals. I suspect you are asking for implicit type coercion, which if present could possibly replace some of the existing LiteralConvertible protocols..

-DW

···

On Apr 14, 2016, at 10:27 AM, Milos Rankovic via swift-evolution <swift-evolution@swift.org> wrote:

5

Hey, Milos!

Can you please give us a few real-world examples where initializing a nontrivial tree-like data structure in code would be useful?

It's an honest question — I have never felt the need in my life, and I always preferred to move the data into something like a bundled json or CSV, rather than providing it in code.

A.

···

On Apr 14, 2016, at 10:27 PM, Milos Rankovic via swift-evolution <swift-evolution@swift.org> wrote:

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating an array, but a tree – a more general structure of which arrays are only a special case. Given the well-deserved and growing reputation of Swift, one would hope that in this instance the compiler would be able to default to something like a:

enum Tree<Value> {
  case Leaf(Value)
  case Branches([Tree])
}

extension Tree : ArrayLiteralConvertible {
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
}

For this to work in the playground, however, we must manually lift the values into the world of trees first. And to make that chore in turn easier on the eye we can introduce a:

prefix operator ◊ {} // looks a bit like a leaf (us/uk kbd: ⎇⇧V)
prefix func ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

The point here is that if adding such a fundamental type to the Standard Library would not be a priority at present, it is not the end of the world since we can easily enough write it ourselves… What we cannot do ourselves, however, is to get rid of the need for that operator in the common scenario of initialising with literal values. For this we need a literal-convertible protocol requiring two initialisers:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

And, whilst we are at it, we could also get rid of the need for that operator in the case of nested associative arrays (again, you can try this in the playground):

enum DictionaryTree<Key, Value> {
  case Leaf(Value)
  case Branches([(Key, DictionaryTree)])
}

extension DictionaryTree : DictionaryLiteralConvertible {
  init(dictionaryLiteral pairs: (Key, DictionaryTree)...) {
    self = .Branches(pairs)
  }
}

prefix func ◊ <Key, Value> (leaf: Value) -> DictionaryTree<Key, Value> { return .Leaf(leaf) }

let map: DictionaryTree<String,Int> = [
  "A" : [:],
  "B" : [
    "Ba" : ◊0,
    "Bb" : ◊0,
    "Bc" : [
      "Bc1" : ◊0,
      "Bc2" : ◊0,
      "Bc3" : ◊0
    ]
  ]
]

… by introducing an analogous protocol:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Please note: I do understand that fleshing out these structures (along with all the juicy methods, operators and lazy alternatives) may not currently be a priority for Swift. The two literal-convertible protocols however, may be a much less daunting task, which would open to us some very useful programming idioms…

milos
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

6

I mean, you could just make your Tree type implement all the individual literal-convertible protocols.

John.

···

On Apr 14, 2016, at 12:01 PM, Milos Rankovic via swift-evolution <swift-evolution@swift.org> wrote:
Hi Andrey and Laurent,

On 14 Apr 2016, at 19:23, Andrey Tarantsov <andrey@tarantsov.com <mailto:andrey@tarantsov.com>> wrote:

Can you please give us a few real-world examples where initializing a nontrivial tree-like data structure in code would be useful?

It's an honest question — I have never felt the need in my life, and I always preferred to move the data into something like a bundled json or CSV, rather than providing it in code.

I suppose we always prefer to move *all* data into databases or files with dedicated data formats, *including* arrays, strings, dictionaries, etc. Sure. But it would be rather underwhelming if you could not also just instantiate an array or a string from a literal.

On 14 Apr 2016, at 19:33, L Mihalkovic <laurent.mihalkovic@gmail.com <mailto:laurent.mihalkovic@gmail.com>> wrote:

I’d rather the language do NOT make it easy to have complex literals initializations

I agree, except, something like `[1, [2]]` doesn’t immediately strike me by its complexity. Likewise, I find it a little deflating that I cannot express a piece of JSON in code. My example structures do allow you to write:

let _: DictionaryTree<String, String> =
[
  "name": ◊"Johnny Appleseed",
  "address": [
    "streetAddress": ◊"21 2nd Street",
    "city": ◊"New York"
  ]
]

… but I cannot get rid of that prefix operator without the additional literal-convertible protocols. Given the *simplicity* of these structures, it seems it should not be beyond Swift to represent them in code with ease and elegance. And to begin with, all we need are those couple of protocols.

7

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

This would be easily done with conditional conformance; as it is, you'll simply have to make your Tree less generic, e.g. by always requiring Value to be IntegerLiteralConvertible. Of course, this would not be a problem for a JSON tree, which would not be generic at all.

John.

···

On Apr 14, 2016, at 1:34 PM, Milos Rankovic <milos@milos-and-slavica.net> wrote:
Hi John,

On 14 Apr 2016, at 21:09, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

I mean, you could just make your Tree type implement all the individual literal-convertible protocols.

It does sound like something like that should be doable, but it isn’t. The literal-convertible protocols only require one initialiser, but you need two: one that lifts leaf values to Self and the other that actually takes Self elements (it is this last one that provides for recursion). In other words, we’d need to overload our conformance:

extension Tree : ArrayLiteralConvertible { // error: does not conform!
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
  init(arrayLiteral elements: Value...) {
    if elements.count == 1 { self = .Leaf(elements[0]) }
    else { self = .Branches(elements.map{ .Leaf($0) }) }
  }
}

But you can only conform in one or the other way, but not both! Therefore, for trees, we need something like:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

8

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

That not only doesn't work if your type isn't a LiteralConvertible, it also doesn't work if you want to build a literal with variables:

  let myTree: Tree = [1, [2, three]]

The real missing feature here is implicit lifting like Optional offers. With a LiftingConvertible protocol, you could say something like this:

  enum Tree<Value> {
    case leaf(Value)
    case branches([Tree<Value>])
  }
  
  extension Tree: ArrayLiteralConvertible {
    init(arrayLiteral branches: Tree<Value>...) {
      self = .branches(branches)
    }
  }
  
  extension Tree: LiftingConvertible {
    init(lifting value: Value) {
      self = .leaf(value)
    }
  }

However, even without implicit lifting, you should still be able to write trees with just ArrayLiteralConvertible by explicitly lifting the leaves:

  let myTree: Tree = [.leaf(1), [.leaf(2), .leaf(three)]]

That isn't great, but it's not awful, either.

For that matter, you could write a semi-implicit lifting feature:

  protocol LiftingConvertible {
    associatedtype Lifted
    init(lifting value: Lifted)
  }
  
  prefix operator ^ {}
  prefix func ^ <Lifting: LiftingConvertible> (lifted: Lifting.Lifted) -> Lifting {
    return Lifting(lifting: lifted)
  }
  
  let myTree: Tree = [^1, [^2, ^three]]

That's actually not so bad.

···

--
Brent Royal-Gordon
Architechies

9

Note that all of your examples rely not just on recursion but on heterogeneous recursion, so the multiple-conformance idea doesn't work. Fundamentally, your trees have a payload type that needs to be constructible from different kinds of literal. It's appropriate to model that with conformance to multiple protocols. The ability to do that conditionally based on whether another type declares a conformance is called "conditional conformance", and it's already something we're strongly considering for the future; it's just not an easy feature to actually implement.

John.

···

On Apr 14, 2016, at 2:03 PM, Milos Rankovic <milos@milos-and-slavica.net> wrote:

On 14 Apr 2016, at 21:36, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

You mean this:

public enum IntTree {
  case Leaf(Int)
  case Branches([IntTree])
}

extension IntTree : ArrayLiteralConvertible {
  public init(arrayLiteral elements: IntTree...) {
    self = .Branches(elements)
  }
}

extension IntTree : IntegerLiteralConvertible {
  public init(integerLiteral value: IntegerLiteralType) {
    self = .Leaf(value)
  }
}

let tree: IntTree = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

you'll simply have to make your Tree less generic

Yep, that’s the rub… With generic trees you can express yourself freely, whether you feel like:

import SpriteKit

let actionTree: Tree<SKAction> = [
  ◊.waitForDuration(1),
  [
    ◊.fadeInWithDuration(1),
    ◊.scaleTo(1, duration: 1)
  ],
  ◊.playSoundFileNamed("TaDa", waitForCompletion: false)
]

… or:

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "address": [
    "house_number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊"New York"
  ]
]

I’d just love to get rid of that prefix operator…

10

Another name for this feature is "user-defined implicit conversions".

John.

···

On Apr 14, 2016, at 2:20 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

That not only doesn't work if your type isn't a LiteralConvertible, it also doesn't work if you want to build a literal with variables:

  let myTree: Tree = [1, [2, three]]

The real missing feature here is implicit lifting like Optional offers. With a LiftingConvertible protocol, you could say something like this:

  enum Tree<Value> {
    case leaf(Value)
    case branches([Tree<Value>])
  }
  
  extension Tree: ArrayLiteralConvertible {
    init(arrayLiteral branches: Tree<Value>...) {
      self = .branches(branches)
    }
  }
  
  extension Tree: LiftingConvertible {
    init(lifting value: Value) {
      self = .leaf(value)
    }
  }

11

  extension Tree: LiftingConvertible {
    init(lifting value: Value) {
      self = .leaf(value)
    }
  }

Another name for this feature is "user-defined implicit conversions".

This is absolutely a form of user-defined implicit conversion. It's a limited form (one possible `Lifted` for each `LiftingConvertible`), which may help make it more feasible, and it is basically a generalization of the special-cased Optional lifting, but it is a user-defined implicit conversion.

I understand and agree with the reasons for deferring implicit conversions. What I'm saying is that seeing this as a "tree literals" feature is a very narrow view of the overall problem.

···

--
Brent Royal-Gordon
Architechies

12

The topic’s come up before. I’m in favor of it, but IIRC there are two problems that need to be resolved first:

(I *think* I’m remembering this correctly… don’t quote me on this…)

First, it can cause the type-checker to become “pathological”.
Second, it can cause some *very* unexpected behavior if things are implicitly converted through different types than you thought.

- Dave Sweeris

···

On Apr 14, 2016, at 4:24 PM, John McCall via swift-evolution <swift-evolution@swift.org> wrote:

On Apr 14, 2016, at 2:20 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

That not only doesn't work if your type isn't a LiteralConvertible, it also doesn't work if you want to build a literal with variables:

  let myTree: Tree = [1, [2, three]]

The real missing feature here is implicit lifting like Optional offers. With a LiftingConvertible protocol, you could say something like this:

  enum Tree<Value> {
    case leaf(Value)
    case branches([Tree<Value>])
  }
  
  extension Tree: ArrayLiteralConvertible {
    init(arrayLiteral branches: Tree<Value>...) {
      self = .branches(branches)
    }
  }
  
  extension Tree: LiftingConvertible {
    init(lifting value: Value) {
      self = .leaf(value)
    }
  }

Another name for this feature is "user-defined implicit conversions".

John.
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

13

Thanks for the comment, Vladimir.

···

On 14 Apr 2016, at 18:14, Vladimir.S <svabox@gmail.com> wrote:

Well, actually we can compile :

var zz : [Any] = [[Int](), 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

Sure. I just wasn’t sure it was worth mentioning (it was a long post anyway): annotating the variable with `[Any]` is not preserving the leaf type nor does it do justice to the overall structure.

milos

14

Hi John and Brent,

multiple-conformance idea doesn't work

The idea is not multiple-conformance (or overloading), but multiple (two) initialisers required by the literal-convertible protocols:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

… and:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Note that all of your examples rely not just on recursion but on heterogeneous recursion

The crux of the matter is not heterogeneity in general, but of the leaf value in particular. This is what Brent is addressing. All my examples, save one, had a uniform leaf value type (even the Tree<SKAction> example).

The heterogeneity that I'm referring to is the mix of sub-trees and leaves at a single level.

The one exception is my second JSON example. There I did not post the lift operator overload as you can probably imagine it. Minimally:

It's pretty implausible that we'd ever add a "tree literal" concept that serves exactly your use case, so I'm looking for ways to capture it that fit within the existing language framework, or at least take advantage of a more general addition to the language.

Your JSON literal example is already pretty well modeled by simply making a JSONValue type that conforms to all the literal protocols. It is completely unclear why you would even want to model this with some generic Tree structure. Note that neither your tree-literal-protocol proposal nor Brent's lifting-protocol proposal is actually adequate for embedding non-literal Int/Double/Bool values in the structure because they both only allow a single "leaf" type.

Your other examples could be modeled with either a lifting protocol or a conditional conformance. I was just noting that the conditional conformance would be adequate if you were willing to manually lift non-literal values, and conditional conformances are a feature that's already basically planned, as opposed to a new research project.

John.

···

On Apr 14, 2016, at 2:56 PM, Milos Rankovic <milos@milos-and-slavica.net> wrote:

On 14 Apr 2016, at 22:22, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

enum JSONValue {
  case Text(String)
  case Integer(Int)
}

prefix func ◊ <Key> (leaf: String) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Text(leaf))
}

prefix func ◊ <Key> (leaf: Int) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Integer(leaf))
}

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "address": [
    "house_number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊"New York"
  ]
]

Notice in particular how much contextual information you are getting from the expected return type. Still though, as Brent, points out, this won’t work with the two literal-convertable protocols. Nevertheless, I’d be very happy if they could be added as a first step since I suspect that would be the easiest option and one that would still allow for all my examples so far to work without the lift operator; all except this `JSONValue` example.

milos

15

Hi Andrey and Laurent,

Can you please give us a few real-world examples where initializing a nontrivial tree-like data structure in code would be useful?

It's an honest question — I have never felt the need in my life, and I always preferred to move the data into something like a bundled json or CSV, rather than providing it in code.

I suppose we always prefer to move *all* data into databases or files with dedicated data formats, *including* arrays, strings, dictionaries, etc. Sure. But it would be rather underwhelming if you could not also just instantiate an array or a string from a literal.

I’d rather the language do NOT make it easy to have complex literals initializations

I agree, except, something like `[1, [2]]` doesn’t immediately strike me by its complexity. Likewise, I find it a little deflating that I cannot express a piece of JSON in code. My example structures do allow you to write:

let _: DictionaryTree<String, String> =
[
  "name": ◊"Johnny Appleseed",
  "address": [
    "streetAddress": ◊"21 2nd Street",
    "city": ◊"New York"
  ]
]

… but I cannot get rid of that prefix operator without the additional literal-convertible protocols. Given the *simplicity* of these structures, it seems it should not be beyond Swift to represent them in code with ease and elegance. And to begin with, all we need are those couple of protocols.

milos

···

On 14 Apr 2016, at 19:23, Andrey Tarantsov <andrey@tarantsov.com> wrote:
On 14 Apr 2016, at 19:33, L Mihalkovic <laurent.mihalkovic@gmail.com> wrote:

16

Hey, Milos!

Can you please give us a few real-world examples where initializing a nontrivial tree-like data structure in code would be useful?

It's an honest question — I have never felt the need in my life, and I always preferred to move the data into something like a bundled json or CSV, rather than providing it in code.

A.

ditto.
This is where in the simplest case I write a simple text(json) file, and in the more extreme cases, write a custom DSL+Eclipse Editor to deal with a complete custom file format (I said extreme.. but I did do it). I would even go further.. I’d rather the language do NOT make it easy to have complex literals initializations to avoid having to chase critical CONFIG elements in the source code. D has an interesting concept if you REALLY want do data in code: import (“data_in_code.d”)

···

On Apr 14, 2016, at 8:23 PM, Andrey Tarantsov via swift-evolution <swift-evolution@swift.org> wrote:

On Apr 14, 2016, at 10:27 PM, Milos Rankovic via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

In Swift, we cannot compile:

_ = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

The reason for the compile-time error is that we are not in fact creating an array, but a tree – a more general structure of which arrays are only a special case. Given the well-deserved and growing reputation of Swift, one would hope that in this instance the compiler would be able to default to something like a:

enum Tree<Value> {
  case Leaf(Value)
  case Branches([Tree])
}

extension Tree : ArrayLiteralConvertible {
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
}

For this to work in the playground, however, we must manually lift the values into the world of trees first. And to make that chore in turn easier on the eye we can introduce a:

prefix operator ◊ {} // looks a bit like a leaf (us/uk kbd: ⎇⇧V)
prefix func ◊ <T> (leaf: T) -> Tree<T> { return .Leaf(leaf) }

let tree: Tree<Int> = [, ◊1, [◊2, ◊3], [[◊4, ◊5], [◊6, ◊7], [◊8, ◊9]]]

The point here is that if adding such a fundamental type to the Standard Library would not be a priority at present, it is not the end of the world since we can easily enough write it ourselves… What we cannot do ourselves, however, is to get rid of the need for that operator in the common scenario of initialising with literal values. For this we need a literal-convertible protocol requiring two initialisers:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

Then we could simply:

let tree: Tree<Int> = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

And, whilst we are at it, we could also get rid of the need for that operator in the case of nested associative arrays (again, you can try this in the playground):

enum DictionaryTree<Key, Value> {
  case Leaf(Value)
  case Branches([(Key, DictionaryTree)])
}

extension DictionaryTree : DictionaryLiteralConvertible {
  init(dictionaryLiteral pairs: (Key, DictionaryTree)...) {
    self = .Branches(pairs)
  }
}

prefix func ◊ <Key, Value> (leaf: Value) -> DictionaryTree<Key, Value> { return .Leaf(leaf) }

let map: DictionaryTree<String,Int> = [
  "A" : [:],
  "B" : [
    "Ba" : ◊0,
    "Bb" : ◊0,
    "Bc" : [
      "Bc1" : ◊0,
      "Bc2" : ◊0,
      "Bc3" : ◊0
    ]
  ]
]

… by introducing an analogous protocol:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Please note: I do understand that fleshing out these structures (along with all the juicy methods, operators and lazy alternatives) may not currently be a priority for Swift. The two literal-convertible protocols however, may be a much less daunting task, which would open to us some very useful programming idioms…

milos
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

17

Hi John,

I mean, you could just make your Tree type implement all the individual literal-convertible protocols.

It does sound like something like that should be doable, but it isn’t. The literal-convertible protocols only require one initialiser, but you need two: one that lifts leaf values to Self and the other that actually takes Self elements (it is this last one that provides for recursion). In other words, we’d need to overload our conformance:

extension Tree : ArrayLiteralConvertible { // error: does not conform!
  init(arrayLiteral elements: Tree...) {
    self = .Branches(elements)
  }
  init(arrayLiteral elements: Value...) {
    if elements.count == 1 { self = .Leaf(elements[0]) }
    else { self = .Branches(elements.map{ .Leaf($0) }) }
  }
}

But you can only conform in one or the other way, but not both! Therefore, for trees, we need something like:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

milos

···

On 14 Apr 2016, at 21:09, John McCall <rjmccall@apple.com> wrote:

18

No, you just need Tree to conform to both ArrayLiteralConvertible and IntegerLiteralConvertible, and it implements the latter by building a Value out of it.

You mean this:

public enum IntTree {
  case Leaf(Int)
  case Branches([IntTree])
}

extension IntTree : ArrayLiteralConvertible {
  public init(arrayLiteral elements: IntTree...) {
    self = .Branches(elements)
  }
}

extension IntTree : IntegerLiteralConvertible {
  public init(integerLiteral value: IntegerLiteralType) {
    self = .Leaf(value)
  }
}

let tree: IntTree = [, 1, [2, 3], [[4, 5], [6, 7], [8, 9]]]

you'll simply have to make your Tree less generic

Yep, that’s the rub… With generic trees you can express yourself freely, whether you feel like:

import SpriteKit

let actionTree: Tree<SKAction> = [
  ◊.waitForDuration(1),
  [
    ◊.fadeInWithDuration(1),
    ◊.scaleTo(1, duration: 1)
  ],
  ◊.playSoundFileNamed("TaDa", waitForCompletion: false)
]

… or:

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "address": [
    "house_number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊"New York"
  ]
]

I’d just love to get rid of that prefix operator…

milos

···

On 14 Apr 2016, at 21:36, John McCall <rjmccall@apple.com> wrote:

19

Hi John and Brent,

multiple-conformance idea doesn't work

The idea is not multiple-conformance (or overloading), but multiple (two) initialisers required by the literal-convertible protocols:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

… and:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Note that all of your examples rely not just on recursion but on heterogeneous recursion

The crux of the matter is not heterogeneity in general, but of the leaf value in particular. This is what Brent is addressing. All my examples, save one, had a uniform leaf value type (even the Tree<SKAction> example). The one exception is my second JSON example. There I did not post the lift operator overload as you can probably imagine it. Minimally:

enum JSONValue {
  case Text(String)
  case Integer(Int)
}

prefix func ◊ <Key> (leaf: String) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Text(leaf))
}

prefix func ◊ <Key> (leaf: Int) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Integer(leaf))
}

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "address": [
    "house_number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊"New York"
  ]
]

Notice in particular how much contextual information you are getting from the expected return type. Still though, as Brent, points out, this won’t work with the two literal-convertable protocols. Nevertheless, I’d be very happy if they could be added as a first step since I suspect that would be the easiest option and one that would still allow for all my examples so far to work without the lift operator; all except this `JSONValue` example.

milos

···

On 14 Apr 2016, at 22:22, John McCall <rjmccall@apple.com> wrote:

20

The heterogeneity that I'm referring to is the mix of sub-trees and leaves at a single level.

… which is why I was making the point that that part of the heterogeneity problem is solved.

Your JSON literal example is already pretty well modeled by simply making a JSONValue type that conforms to all the literal protocols. It is completely unclear why you would even want to model this with some generic Tree structure.

Because JSON has the structure of a tree. A dictionary of the type `[String:AnyObject]` does not express that structure even if at run-time it turns out that some of those any-objects are themselves dictionaries. `Tree<String, JSONValue>`, in contrast, precisely expresses the structure of JSON objects. `[String:JSONValue]` is flat so it is not worth talking about, whilst some dedicated `JSON` enum is just that, a dedicated type that is the symptom of a language incapable of representing things like `[1, [2]]` as such.

You do have a good point about conforming JSONValue type to the literal-convertible protocols. That is important here because it reminds us that the question of converting Int and String values to JSONValue type in my example is a completely separate issue from my proposal. This in turn shows that the two tree literal-convertable protocols I’d love to see added to the Standard Library would be sufficient in all cases. For instance (assuming the code from my original post is already in the context):

enum JSONValue {
  case Integer(Int)
  case Text(String)
  case URL(NSURL)

  init(_ string: String) {
    if let url = NSURL(string: string) {
      self = .URL(url)
    } else {
      self = .Text(string)
    }
  }
}

extension JSONValue : UnicodeScalarLiteralConvertible {
  init(unicodeScalarLiteral value: String) { self.init(value) }
}
extension JSONValue : ExtendedGraphemeClusterLiteralConvertible {
  init(extendedGraphemeClusterLiteral value: String) { self.init(value) }
}
extension JSONValue : StringLiteralConvertible {
  init(stringLiteral value: String){ self.init(value) }
}

extension JSONValue : IntegerLiteralConvertible {
  init(integerLiteral value: Int) { self = .Integer(value) }
}

let city: JSONValue = .Text("New York")

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "github": ◊"http://github.com/apple/swift-evolution&quot;,
  "address": [
    "number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊city
  ]
]

This is what we can do already (try it in the playground - even the url is read as a url). However, if we were also given the following protocol:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

… then the lifting of the JSONValue-s into the recursive world of trees would be done by the `init(literal: Self.LeafValue…)` and we would no longer need the lifting operator ◊.

Finally, it is worth mentioning that the two proposed protocols, TreeLiteralConvertible and DictionaryTreeLiteralConvertible, should be simple to implement, would not affect existing code, and would allow us to work with all kinds of trees and nested associative arrays with ease, safety and elegance we are growing accustomed to when programming in Swift.

milos

···

On 15 Apr 2016, at 03:22, John McCall <rjmccall@apple.com> wrote:

On 15 Apr 2016, at 03:22, John McCall <rjmccall@apple.com> wrote:

On Apr 14, 2016, at 2:56 PM, Milos Rankovic <milos@milos-and-slavica.net <mailto:milos@milos-and-slavica.net>> wrote:
Hi John and Brent,

On 14 Apr 2016, at 22:22, John McCall <rjmccall@apple.com <mailto:rjmccall@apple.com>> wrote:

multiple-conformance idea doesn't work

The idea is not multiple-conformance (or overloading), but multiple (two) initialisers required by the literal-convertible protocols:

protocol TreeLiteralConvertible {
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: Self...)
}

… and:

protocol DictionaryTreeLiteralConvertible {
  associatedtype Key
  associatedtype LeafValue
  init(literal: Self.LeafValue...)
  init(literal: (Key, Self)...)
}

Note that all of your examples rely not just on recursion but on heterogeneous recursion

The crux of the matter is not heterogeneity in general, but of the leaf value in particular. This is what Brent is addressing. All my examples, save one, had a uniform leaf value type (even the Tree<SKAction> example).

The heterogeneity that I'm referring to is the mix of sub-trees and leaves at a single level.

The one exception is my second JSON example. There I did not post the lift operator overload as you can probably imagine it. Minimally:

It's pretty implausible that we'd ever add a "tree literal" concept that serves exactly your use case, so I'm looking for ways to capture it that fit within the existing language framework, or at least take advantage of a more general addition to the language.

Your JSON literal example is already pretty well modeled by simply making a JSONValue type that conforms to all the literal protocols. It is completely unclear why you would even want to model this with some generic Tree structure. Note that neither your tree-literal-protocol proposal nor Brent's lifting-protocol proposal is actually adequate for embedding non-literal Int/Double/Bool values in the structure because they both only allow a single "leaf" type.

Your other examples could be modeled with either a lifting protocol or a conditional conformance. I was just noting that the conditional conformance would be adequate if you were willing to manually lift non-literal values, and conditional conformances are a feature that's already basically planned, as opposed to a new research project.

John.

enum JSONValue {
  case Text(String)
  case Integer(Int)
}

prefix func ◊ <Key> (leaf: String) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Text(leaf))
}

prefix func ◊ <Key> (leaf: Int) -> DictionaryTree<Key, JSONValue> {
  return .Leaf(.Integer(leaf))
}

let johnny: DictionaryTree<String, JSONValue> =
[
  "name": ◊"Johnny Appleseed",
  "age": ◊25,
  "address": [
    "house_number": ◊21,
    "street": ◊"2nd Street",
    "city": ◊"New York"
  ]
]

Notice in particular how much contextual information you are getting from the expected return type. Still though, as Brent, points out, this won’t work with the two literal-convertable protocols. Nevertheless, I’d be very happy if they could be added as a first step since I suspect that would be the easiest option and one that would still allow for all my examples so far to work without the lift operator; all except this `JSONValue` example.

milos