sum types, recursive types, algebraic datatypes

[dckc]

I was excited by the prospect that mypy would bring algebraic data types to python...

"A general algebraic data type is a possibly recursive sum type of product types."

• https://en.wikipedia.org/wiki/Algebraic_data_type

The tuple type is clearly a product type, and mypy has union types, but the tutorial makes them look like something other than ordinary sum types.

http://www.mypy-lang.org/tutorial.html#uniontypes

Are sum types and recursive types planned?

[JukkaL]

Yeah, the planned union types are not really like ML-style sum types. They aren't like C unions either, which makes them a bit confusing.

However, we could have something like case classes in Scala. I'm not sure how to support pattern matching, though. A series of isinstance tests is always possible, but it's more limited.

[dckc]

Case classes (along with sealed abstract classes) in Scala work fine a sum types, though they're a little verbose. But yeah, pattern matching is an essential part of the package. Hmm.

[JukkaL]

Closing this as there hasn't been any activity in a long time.

[averagehat]

It seems like NamedTuples can operate like case classes. Does anything about mypy's Union make it incapable of representing sum types? From the docstring it seems like it would be okay . . .

I see no way of representing recursively defined NamedTuples with python semantics, however, because anything like the following won't compile

Node = NamedTuple("Node", [("value", Node), ("left", Node)])

I wonder if anyone else has any thoughts now that some time has passed?

[dckc]

Yes, a python namedtuple is like a scala case class. But these are product types. A scala sum type is formed when several different case classes extend one sealed base class.

[averagehat]

Right. So the mypy equivalent could be:

Blue = NamedTuple("Blue", [])
Green = NamedTuple("Green", [])

Cat = NamedTuple("Cat", [("name", str)])
Fish = NamedTuple("Fish",   [("name", str), ("color", Color)])
Squid = NamedTuple("Squid", [("name", str), ("age", int)])

Pet = Union[Cat,Fish,Squid]
Color = Union[Green,Blue]

def a_pet() -> Pet:   #passes 
    return Cat("neko")
def not_a_pet() -> Pet:  #fails
    return Blue()

I was suggesting that Union was powerful enough to represent sum types.

aside: hmmm, I wonder if it would be possible to have some kind of "pattern-match" exhaustion checks? It seems like the enforced check on Optional is a special case of this.

[dckc]

I just ran into the lack of recursive unions again. Ouch

I wanted to do:

State = Dict[str, Union[BinaryIO, 'State']]

[orenbenkiki]

The lack of recursive types makes it necessary to hack around any kind of a tree type. For example, it isn't possible to describe the type of the common flatten function (which should be something like Tree[T] = Union[T, List[Tree[T]]] - both recursive and generic).

[blakehawkins]

Without product types, I have no way of demanding in my API that a function argument is a class that implements two different Mixins, e.g.

def check_sprinter_is_ready(sprinter: Product[PositionMixin, VelocityMixin]):
    pass

[dckc]

Mypy has product types: Tuple and NamedTuple.

…

On Thu, Apr 19, 2018, 9:15 AM blakehawkins ***@***.***> wrote: Without product types, I have no way of demanding in my API that a function argument is a class that implements two different Mixins, e.g. def check_sprinter_is_ready(sprinter: Product[PositionMixin, VelocityMixin]): pass — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#256 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAJNykREWHiGSAvL4HV8Ro3G5C7sENmSks5tqKocgaJpZM4A2fPB> .

[ilevkivskyi]

@blakehawkins What you need is an Intersection. There is an old proposal about this, but from my feelings it will be not implemented this year. If those mixins are structural (i.e. you don't care about inheriting from them actually) then you can define them as protocols, then your problem is solved. But for nominal classes, sorry you will need to wait for intersection types (and better don't call them product types to not confuse people).

[blakehawkins]

@ilevkivskyi yep that's exactly what's needed - thanks for the comments.

python/typing#213

[carymrobbins]

I don't use mypy, but happened to come across this thread. Maybe something like the following encoding would work? I'm not sure exactly how mypy's type checker works, I assume it operates on an AST level, so it could maybe handle this.

def Node():
    return NamedTuple("Node", [("value", Node), ("left", Node)])

Or maybe even

Node = lambda: NamedTuple("Node", [("value", Node), ("left", Node)])

[xieyuheng]

Python 3.12 can run (and pyright can check) this recursive ADT:

• pyright playground

from dataclasses import dataclass

type Exp = Var | Ap | Fn | Let

@dataclass
class Var:
    name: str

@dataclass
class Ap:
    target: Exp
    arg: Exp

@dataclass
class Fn:
    name: str
    ret: Exp

@dataclass
class Binding:
  name: str
  exp: Exp

@dataclass
class Let:
  bindings: list[Binding]
  body: Exp


def format_exp(exp: Exp) -> str:
    match exp:
        case Var(name):
            return name
        case Ap(target, arg):
            return f"({format_exp(target)} {format_exp(arg)})"
        case Fn(name, ret):
            return f"(lambda ({name}) {format_exp(ret)})"
        case Let(bindings, body):
            bindings_text = ' '.join(map(format_binding, bindings))
            return f"(let ({bindings_text}) {format_exp(body)})"


def format_binding(binding: Binding) -> str:
    return f"[{binding.name} {format_exp(binding.exp)}]"


print(format_exp(Var("x")))
print(format_exp(Ap(Var("f"), Var("x"))))
print(format_exp(Fn("x", Ap(Var("f"), Var("x")))))
print(format_exp(Let([
    Binding("x", Ap(Var("f"), Var("x"))),
    Binding("y", Ap(Var("f"), Var("x")))
], Ap(Var("x"), Var("y")))))