Problem with recursive tree type defined in terms of List

Learn
1

Hi,

I’m just starting out with Elm and I’m having trouble with the following code. Perhaps someone can help me out.

The idea is to define an AltTree type where some nodes can have multiple alternate subtrees with one of the choices selected. I then have a decide function of type AltTree a -> Tree a whose job it is to “evaluate” all the choices. Here is the code:

module AltTree exposing (..)

import Array exposing (Array)

type Tree a = Node (List a) | Leaf a

type AltTree a = Seq (List (AltTree a)) | Choice Int (Array (AltTree a)) | AltLeaf a

decide : AltTree a -> Tree a
decide tree =
    case tree of
        Seq subtrees ->
            Node (List.map decide subtrees)
        Choice i subtrees ->
            case (Array.get i subtrees) of
                Just x -> decide x
                Nothing -> Node [] 
        AltLeaf x ->
            Leaf x

This fails to compile with:

-- TYPE MISMATCH ----------------------------------------------- src/AltTree.elm

Something is off with the 1st branch of this `case` expression:

13|             Node (List.map decide subtrees)
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This `Node` call produces:

    Tree (Tree a)

But the type annotation on `decide` says it should be:

    Tree a

Hint: Your type annotation uses type variable `a` which means ANY type of value
can flow through, but your code is saying it specifically wants a `Tree` value.
Maybe change your type annotation to be more specific? Maybe change the code to
be more general?

Read <https://elm-lang.org/0.19.0/type-annotations> for more advice!

I sort of get why this would happen, but I can’t seem to work around it. Every attempt at defining some sort of concatTrees : List (Tree a) -> Tree a function to solve the problem has failed with similar error messages.

Any solutions or ideas? Is there something totally misguided in what I’m attempting?

Thanks!

2

Found the solution in the end. The problem was not with decide but with the Tree type, which should have been type Tree = Node (List (Tree a)) | Leaf a instead of type Tree = Node (List a) | Leaf a.

1 Like
3

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.