Proposal: canonical data for simple linked list

Exercism
,
1

The simple-linked-list exercise is implemented in 31 tracks … but there is no canonical data. However, looking through the tests on those tracks, I saw quite a bit of overlap and common tests.

I propose to add following canonical data to to the problem specs.

Due to size limits, I need to split it across posts :frowning:

For easier reading, I also attached a rendered-code version (below).

Proposed cases, JSON, part 1/2 
{
  "cases": [
    {
      "description": "count",
      "cases": [
        {
          "uuid": "TBD",
          "description": "Empty list has length of zero",
          "property": "list",
          "input": {
            "initialValues": [],
            "operations": [
              {
                "operation": "count",
                "expected": 0
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Singleton list has length of one",
          "property": "list",
          "input": {
            "initialValues": [1],
            "operations": [
              {
                "operation": "count",
                "expected": 1
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Non-empty list has correct length",
          "property": "list",
          "input": {
            "initialValues": [1, 2,3 ],
            "operations": [
              {
                "operation": "count",
                "expected": 3
              }
            ]
          },
          "expected": {}
        }
      ]
    },
    {
      "description": "pop",
      "cases": [
        {
          "uuid": "TBD",
          "description": "Pop from empty list is an error",
          "property": "list",
          "input": {
            "initialValues": [],
            "operations": [
              {
                "operation": "pop",
                "expected": {
                  "error": "list is empty"
                }
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can pop from singleton list",
          "property": "list",
          "input": {
            "initialValues": [1],
            "operations": [
              {
                "operation": "pop",
                "expected": 1
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can pop from non-empty list",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "pop",
                "expected": 2
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can pop multiple items",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "pop",
                "expected": 2
              },
              {
                "operation": "pop",
                "expected": 1
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Pop updates the count",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "count",
                "expected": 2
              },
              {
                "operation": "pop",
                "expected": 2
              },
              {
                "operation": "count",
                "expected": 1
              },
              {
                "operation": "pop",
                "expected": 1
              },
              {
                "operation": "count",
                "expected": 0
              }
            ]
          },
          "expected": {}
        }
      ]
    },
    {
      "description": "push",
      "cases": [
        {
          "uuid": "TBD",
          "description": "Can push to an empty list",
          "property": "list",
          "input": {
            "operations": [
              {
                "operation": "push",
                "value": 1
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can push to a non-empty list",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "push",
                "value": 3
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Push updates count",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "push",
                "value": 3
              },
              {
                "operation": "count",
                "expected": 3
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Push and pop",
          "property": "list",
          "input": {
            "initialValues": [],
            "operations": [
              {
                "operation": "push",
                "value": 1
              },
              {
                "operation": "push",
                "value": 2
              },
              {
                "operation": "pop",
                "expected": 2
              },
              {
                "operation": "push",
                "value": 3
              },
              {
                "operation": "count",
                "expected": 2
              },
              {
                "operation": "pop",
                "expected": 3
              },
              {
                "operation": "pop",
                "expected": 1
              },
              {
                "operation": "count",
                "expected": 0
              }
            ]
          },
          "expected": {}
        }
      ]
    },
    {
      "description": "peek",
      "cases": [
        {
          "uuid": "TBD",
          "description": "Peek on empty list is an error",
          "property": "list",
          "input": {
            "initialValues": [],
            "operations": [
              {
                "operation": "peek",
                "expected": {
                  "error": "list is empty"
                }
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can peek on singleton list",
          "property": "list",
          "input": {
            "initialValues": [1],
            "operations": [
              {
                "operation": "peek",
                "expected": 1
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can peek on non-empty list",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "peek",
                "expected": 2
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Peek does not change the count",
          "property": "list",
          "input": {
            "initialValues": [1, 2],
            "operations": [
              {
                "operation": "peek",
                "expected": 2
              },
              {
                "operation": "count",
                "expected": 2
              }
            ]
          },
          "expected": {}
        },
        {
          "uuid": "TBD",
          "description": "Can peek after a pop and push",
          "property": "list",
          "input": {
            "initialValues": [],
            "operations": [
              {
                "operation": "push",
                "value": 1
              },
              {
                "operation": "push",
                "value": 2
              },
              {
                "operation": "peek",
                "expected": 2
              },
              {
                "operation": "pop",
                "value": 2
              },
              {
                "operation": "peek",
                "expected": 1
              },
              {
                "operation": "push",
                "value": 3
              },
              {
                "operation": "peek",
                "expected": 3
              }
            ]
          },
          "expected": {}
        }
      ]
    },
[...]
2 Likes
2
Proposed cases, JSON, part 2/2 
{
  "description": "toList",
  "cases": [
    {
      "uuid": "TBD",
      "description": "Empty linked list to list is empty",
      "property": "list",
      "input": {
        "initialValues": [],
        "operations": [
          {
            "operation": "toList",
            "expected": []
          }
        ]
      },
      "expected": {}
    },
    {
      "uuid": "TBD",
      "description": "To list with multiple values",
      "property": "list",
      "input": {
        "initialValues": [1, 2, 3],
        "operations": [
          {
            "operation": "toList",
            "expected": [3, 2, 1]
          }
        ]
      },
      "expected": {}
    },
    {
      "uuid": "TBD",
      "description": "To list after a pop",
      "property": "list",
      "input": {
        "initialValues": [],
        "operations": [
          {
            "operation": "push",
            "value": 1
          },
          {
            "operation": "push",
            "value": 2
          },
          {
            "operation": "push",
            "value": 3
          },
          {
            "operation": "pop",
            "expected": 3
          },
          {
            "operation": "push",
            "value": 4
          },
          {
            "operation": "toList",
            "expected": [4, 2, 1]
          }
        ]
      },
      "expected": {}
    }
  ]
},
{
  "description": "reverse",
  "cases": [
    {
      "uuid": "TBD",
      "description": "Reversed empty list is same list",
      "property": "list",
      "input": {
        "initialValues": [],
        "operations": [
          {
            "operation": "reverse"
          },
          {
            "operation": "toList",
            "expected": []
          }
        ]
      },
      "expected": {}
    },
    {
      "uuid": "TBD",
      "description": "Reversed singleton list is same list",
      "property": "list",
      "input": {
        "initialValues": [1],
        "operations": [
          {
            "operation": "reverse"
          },
          {
            "operation": "toList",
            "expected": [1]
          }
        ]
      },
      "expected": {}
    },
    {
      "uuid": "TBD",
      "description": "Reversed non-empty list is reversed",
      "property": "list",
      "input": {
        "initialValues": [1, 2, 3],
        "operations": [
          {
            "operation": "reverse"
          },
          {
            "operation": "toList",
            "expected": [1, 2, 3]
          }
        ]
      },
      "expected": {}
    },
    {
      "uuid": "TBD",
      "description": "Double reverse",
      "property": "list",
      "input": {
        "initialValues": [1, 2, 3],
        "operations": [
          {
            "operation": "reverse"
          },
          {
            "operation": "reverse"
          },
          {
            "operation": "toList",
            "expected": [3, 2, 1]
          }
        ]
      },
      "expected": {}
    }
  ]
}

]
}

3

For easier reading, I rendered the JSON data to pseudo code with a small helper script.

Tests, as code 
=== count ===

# Empty list has length of zero
l = LinkedList([])
l.count() ==> WANT 0

# Singleton list has length of one
l = LinkedList([1])
l.count() ==> WANT 1

# Non-empty list has correct length
l = LinkedList([1, 2, 3])
l.count() ==> WANT 3

=== pop ===

# Pop from empty list is an error
l = LinkedList([])
l.pop() ==> WANT {'error': 'list is empty'}

# Can pop from singleton list
l = LinkedList([1])
l.pop() ==> WANT 1

# Can pop from non-empty list
l = LinkedList([1, 2])
l.pop() ==> WANT 2

# Can pop multiple items
l = LinkedList([1, 2])
l.pop() ==> WANT 2
l.pop() ==> WANT 1

# Pop updates the count
l = LinkedList([1, 2])
l.count() ==> WANT 2
l.pop() ==> WANT 2
l.count() ==> WANT 1
l.pop() ==> WANT 1
l.count() ==> WANT 0

=== push ===

# Can push to an empty list
l = LinkedList(None)
l.push(1)

# Can push to a non-empty list
l = LinkedList([1, 2])
l.push(3)

# Push updates count
l = LinkedList([1, 2])
l.push(3)
l.count() ==> WANT 3

# Push and pop
l = LinkedList([])
l.push(1)
l.push(2)
l.pop() ==> WANT 2
l.push(3)
l.count() ==> WANT 2
l.pop() ==> WANT 3
l.pop() ==> WANT 1
l.count() ==> WANT 0

=== peek ===

# Peek on empty list is an error
l = LinkedList([])
l.peek() ==> WANT {'error': 'list is empty'}

# Can peek on singleton list
l = LinkedList([1])
l.peek() ==> WANT 1

# Can peek on non-empty list
l = LinkedList([1, 2])
l.peek() ==> WANT 2

# Peek does not change the count
l = LinkedList([1, 2])
l.peek() ==> WANT 2
l.count() ==> WANT 2

# Can peek after a pop and push
l = LinkedList([])
l.push(1)
l.push(2)
l.peek() ==> WANT 2
l.pop(2)
l.peek() ==> WANT 1
l.push(3)
l.peek() ==> WANT 3

=== toList ===

# Empty linked list to list is empty
l = LinkedList([])
l.toList() ==> WANT []

# To list with multiple values
l = LinkedList([1, 2, 3])
l.toList() ==> WANT [3, 2, 1]

# To list after a pop
l = LinkedList([])
l.push(1)
l.push(2)
l.push(3)
l.pop() ==> WANT 3
l.push(4)
l.toList() ==> WANT [4, 2, 1]

=== reverse ===

# Reversed empty list is same list
l = LinkedList([])
l.reverse()
l.toList() ==> WANT []

# Reversed singleton list is same list
l = LinkedList([1])
l.reverse()
l.toList() ==> WANT [1]

# Reversed non-empty list is reversed
l = LinkedList([1, 2, 3])
l.reverse()
l.toList() ==> WANT [1, 2, 3]

# Double reverse
l = LinkedList([1, 2, 3])
l.reverse()
l.reverse()
l.toList() ==> WANT [3, 2, 1]

Code used to render the JSON:

Rendering script 
import json
import pathlib

data = json.loads(pathlib.Path("linked_list.json").read_text())
for case in data["cases"]:
    print(f"=== {case["description"]} ===")
    print()
    for c in case["cases"]:
        inp = c["input"]
        print("# " + c["description"])
        print(f"l = LinkedList({inp.get("initialValues")})")
        for op in inp["operations"]:
            if "value" in op:
                print(f"l.{op["operation"]}({op["value"]})")
            elif "expected" in op:
                if isinstance("error", dict):
                    print(f"l.{op["operation"]}() ==> WANT ERROR {op["expected"]}")
                else:
                    print(f"l.{op["operation"]}() ==> WANT {op["expected"]}")
            else:
                print(f"l.{op["operation"]}()")
        print()
1 Like
4

“Non-empty list has correct length” returns wrong count, after a push the count would be 4. I think removing push would be better, since there is a “Push updates count” test after that.

5

I’d expect that, if I create a simple-linked-list from, e.g., ['h', 'i'], then toList would return ['h', 'i'].

Although the internal structure of a simple linked list may make it easier to produce a reversed list, there is nothing in the semantics of the data structure that suggests this behavior. I think this breaks abstraction and may be confusing to students.

We could swap the property names in the toList and reverse tests.

1 Like
6

Fixed.

I would think so, too, but I was matching the data to what exists in the tracks. That’s a good question to consider on the PR once there’s agreement to add canonical data. This post is asking if we should add canonical data, not for a code review ;)

Some data on the ToList. It’s a fairly even split so either way would be messy. We could match the largest number of tracks. We could match the largest number of completed solutions. Or we could tag them by “scenario” and include both. We can discuss this on a PR if/after there’s agreement that we should proceed with adding canonical data (ie the focus of this thread).

LinkedList([1, 2, 3]).toList() == [1, 2, 3]
Tracks: cairo elixir go haskell perl5 pyret red roc rust scala swift unison vlang

LinkedList([1, 2, 3]).toList() == [3, 2, 1]
Tracks: coffeescript erlang fsharp java javascript powershell python ruby tcl vimscript wren
7

Considering that this may affect many different tracks, I think it’s best to discuss this before opening a PR.

That said, I’m +1 on adding canonical data to the exercise, regardless of the decision on this topic.

1 Like
8

+1 for adding canonical data. A scenario seems reasonable to me, but I’d also be curious which tracks have generators in the first place and how many solutions are affected. Perhaps we could split the two sides further by whether they have generators or not and then generate the average number of solutions affected in each group. Pyret for example has no generator so there’s a smidge of work there for me but only four Pyret solutions are affected if we do a breaking change.

9

Given that there’s no canonical data to generate the tests from, I’d guess zero tracks have generators ;) Unless they have their own data.json file then generate tests from?

unison looks like it has … something with JSON. red has a tests.toml file.

LinkedList([1, 2, 3]).toList() == [1, 2, 3]
cairo 2
elixir 944
go 725
haskell 960
perl5
pyret 4
red 15
roc 8
rust 3091
scala 112
swift 156
unison 26
vlang 24
===
6067

LinkedList([1, 2, 3]).toList() == [3, 2, 1]
coffeescript 5
erlang 66
fsharp 145
java 443
javascript 548
powershell 19
python 1266
ruby 576
tcl 10
vimscript 8
wren 9
===
3095
10

In the x86-64-assembly track, the generator (in Python) can take a list of extra cases. This is how simple-linked-list tests were generated.

In the Lean track I’ve opted to allow for an optional extra.json. But this exercise is not implemented in the track yet.

1 Like
11

In the x86-64-assembly track, the generator (in Python) can take a list of extra cases. This is how simple-linked-list tests were generated.

This is how Python does it’s track-only exercises as well. :smile:

Python doesn’t have a generator for this exercise (yet), and the structure of the current proposed data would make for a rather complex one. Not sure I’d want to do that right away, since there are also several methods (peek, toList, and count) that aren’t even implemented (at least by those names) in the exercise as it stands. So those 1200 or so completions would be completely invalidated - or the template would have to special-case a bunch of stuff, or we’d have to skip all the test cases that are problematic.

But having canonical data is a good thing generally. So +1 to that.

12

I’m not understanding what the breakdown is.

Is the first category tracks with generators, or is the second one? I know Rust has generators, as does Python – but Rust is in the first category and Python’s in the second? What exactly are these numbers showing?

13

My bad. I had a typo there. Updated. The two buckets are,

LinkedList([1, 2, 3]).toList() == [1, 2, 3]
LinkedList([1, 2, 3]).toList() == [3, 2, 1]

ie when converting to a list, is the list “reversed” or not.

The per-track naming/existence of the methods is pretty … varied. I could try to make the tests a bit more “clean” and limit the number of methods used so it’s easier for tracks to select which tests they want. Though it might be simpler for tracks to run the operation names through a static mapping to translate them to what the track wants to use. For example, a peek might be list.head().data(). Or tracks don’t have to use the canonical data ;)

Given the nearly-50-50 split on the toList behavior, I think it makes sense to provide both via two scenarios and have a comment recommending new implementations, everything else being equal, prefer the first one (whichever that is) so they become more uniform over time.

1 Like
14

The older instructions for this exercise were specific about it being a LIFO stack, so the difference you’re seeing is likely tracks that implemented the exercise before the story was added vs after (or maybe they missed/ignored that bit in the description).

Python’s had enough trouble with this exercise we had to write a pretty elaborate addendum.

Though it might be simpler for tracks to run the operation names through a static mapping to translate them to what the track wants to use. For example, a peek might be list.head().data() .

I’ll see how the data pans out - but as it stands now, I am likely to refuse quite a few tests and then reimplement them in an additional_tests.json, rather than make a complex template that my future self or any other person might misunderstand or munge.

1 Like
15

We’re at +3 for adding canonical data.

I’m +1 for the split buckets as long as there’s a comment addressing the why and suggesting one of the buckets going forward.

For the default bucket, I’m +1 for LinkedList([1, 2, 3]).toList() == [1, 2, 3]. Like oxe-b said, it feels intuitive that If you put in [1, 2, 3], you’d get that order back. If I got the values back reversed, I’d need to create another linked list to get my original list back.

2 Likes
16

For the default bucket, I’m +1 for LinkedList([1, 2, 3]).toList() == [1, 2, 3] . Like oxe-b said, it feels intuitive that If you put in [1, 2, 3] , you’d get that order back. If I got the values back reversed, I’d need to create another linked list to get my original list back.

Sorry, I have to say I am for the opposite, since this exercise on the Python track is explicit in it being a LIFO stack.

17

The “default bucket” would be a comment in the canonical data JSON recommending when implementing this from scratch, everything else being equal, prefer one bucket over the other. It would explicitly not be making any suggestion about existing implementations changing anything. Would that change anything for you?

1 Like
18

+1 here for both as well

19

Not really. No.

Not really sure why there needs to be a preference at all - or consistency between tracks. Maybe the note should read that when implementing, the track should think about what is idiomatic for their language, and leave other details out of it?

3 Likes
20

Yeah, I’m fine without there being a default bucket actually. There’s no clear favorite per the track lists, and even if there were, someone may come along in the future and want to discuss the decision. We can acknowledge the historical divergence in LIFO/FIFO implementations and impartially provide both buckets and don’t suggest one over the other.

1 Like