MLStyle - are recursive ADTs possible

New to Julia
1

Hi,

I’m playing around with MLStyle but can’t seem to get a definition for a cons list to work.

If I try:

@data XX{T} begin
    Nil
    Cons(hd::T, tl::XX{T})
end

I get: ERROR: LoadError: Defining generic enum Nil <: XX{T} is invalid, as Julia does not support generic value.

If I try:

@data XX{T} begin
    Nil()
    Cons(hd::T, tl::XX{T})
end

I get: MethodError: no method matching List.Nil()
The type List.Nil exists, but no method is defined for this combination of argument types when trying to construct it.

2

OK, I’m not sure why, but the solution is less, not more …

@data XX begin
    Nil
    Cons(hd, tl::XX)
end
function sum_list(lst)
    @match lst begin
        Nil => 0
        Cons(h, t) => h + sum_list(t)
    end
end
function printer(lst)
    @match lst begin
      Nil => println("[]")
      Cons(h, t) => begin
        print("$(h) . ")
        printer(t)
      end
    end
end
function make_test_1()
  return Cons(1, Cons(2, Cons(3, Nil)))
end
function make_test_2()
  return Cons("A", Cons("B", Cons("C", Nil)))
end
i = make_test_1()
s = make_test_2()
println("sum_list(i) = $(sum_list(i))")
#sum_list(i) = 6
printer(i)
#1 . 2 . 3 . []
printer(s)
#A . B . C . []
3

except that allows …

function make_test_3()
  return Cons("A", Cons(1.2, Cons("C", Nil)))
end
printer(make_test_3())
#A . 1.2 . C . []

which is not what I want … I want an homogenous list.

Is this the best place to get help?

4

Moshi.jl might do what you want.

using Moshi.Data: @data

julia> @data XX{T} begin
           Nil
           Cons(T, XX{T})
       end


julia> using .XX: Nil, Cons


julia> Cons('a', Cons('b', Nil{Char}()))
Main.XX.var"typeof(XX)"{Char}(Main.XX.var"##Storage#Cons"{Char}('a', Main.XX.var"typeof(XX)"{Char}(Main.XX.var"##Storage#Cons"{Char}('b', Main.XX.var"typeof(XX)"{Char}(Main.XX.var"##Storage#Nil"{Char}())))))

Really ugly representation but I think it’s the right value.

And heterogeneous lists fail like you want:

julia> Cons('a', Cons(1.2, Nil{Char}()))
ERROR: MethodError: no method matching Cons(::Float64, ::Main.XX.var"typeof(XX)"{Char})
The type `Cons` exists, but no method is defined for this combination of argument types when trying to construct it.
5

Representation can be improved with:

import Moshi.Derive: @derive

@derive XX[Show]
1 Like
6

I can’t get Moshi to work … here is my package

module List

using Moshi.Data: @data
using Moshi.Match: @match

export sum_list, make_test_1, make_test_2, printer

@data XX{T} begin
    Nil
    Cons(T, XX{T})
end
function sum_list(lst)
    @match lst begin
        Nil => 0
        Cons(h, t) => h + sum_list(t)
    end
end
function printer(lst)
    @match lst begin
      Nil => println("[]")
      Cons(h, t) => begin
        print("$(h) . ")
        printer(t)
      end
    end
end
function make_test_1()
  return Cons(1, Cons(2, Cons(3, Nil)))
end
function make_test_2()
  return Cons("A", Cons("B", Cons("C", Nil)))
end
end # module List

my test program is just doing this

using Test
using List

@testset "Simple Cons" begin
  s = make_test_2()
  printer(s)
end

I get this error: ERROR: LoadError: UndefVarError: Cons not defined in List

7

You have to do using ..XX: Nil, Cons or use XX.Nil and XX.Cons.

8

OK, that seems strange to need a “using” inside the module that defines those things …

I put the using directly after the @data:

@data XX{T} begin
    Nil
    Cons(T, XX{T})
end
using ..XX: Nil, Cons

and now I get
MethodError: no method matching List.XX.Cons(::String, ::Type{List.XX.Nil{String}})
The type List.XX.Cons exists, but no method is defined for this combination of argument types when trying to construct it.

Closest candidates are:
List.XX.Cons(::T, ::List.XX.var"typeof(XX)"{T}) where T

I get a very similar error whether I have just Nil or Nil{String} in the example construction.

9

You have to instantiate the Nil ADT’s:

function make_test_1()
  return Cons(1, Cons(2, Cons(3, Nil{Int}())))
end
function make_test_2()
  return Cons("A", Cons("B", Cons("C", Nil{String}())))
end
10

Of course, this errors too because the code generated for @match in recursive ADTs seems to be not good, but that’s something you can open an issue about.

11

Thanks for the help people, but I think the lesson may be, I need to give up my functional fetishes when I’m using Julia. Embrace the array! :slight_smile: