Linked List exercise tests imply an immutable list

[theprash]

I think the tests imply that the doubly linked list is expected to be an immutable data structure because:

• All functions return a new version of the list.
• The tests do not check for mutation of the list passed in.
• Most importantly, mkLinkedList is a plain value, not a function, so the empty list at least must be immutable to avoid individual tests affecting each other.

Although immutability is generally preferred in F#, it seems like it would be too difficult to create an immutable doubly linked list for an exercise like this. So I suggest changing the tests so that:

• The functions don't return the new list.
• Tests check for mutation of the list that was passed in.
• mkLinkedList is a function that takes unit.

This would make the requirements clearer and also simplify the tests, which would no longer need lines like this:

let (val''''''', linkedList''''''') = pop linkedList''''''

[ErikSchierboom]

Well, we had this discussion a while ago. Back then, we decided that we would try to make as many exercises use immutable data as possible, which is after all the FP way. However, I can see what you're getting at. The test do look quite strange. What do you feel @robkeim and @jwood803?

[theprash]

I can see the reason for preferring immutability, but there is a time and place for mutation. Currently, this exercise seems like a confusing mix of both, with a description that's gone out of sync with the tests. Almost all of the submitted answers use mutation and even example answer does!

I can see how the tests are almost set up in a way that would allow you to use either approach. That could be a valid way to go, but to be completely flexible, mkLinkedList should be a function.

[ErikSchierboom]

I can totally see what you're getting at. I would just like to get the opinion of someone else. @rmunn @robkeim @jwood803 ?

[robkeim]

I'm definitely for keeping immutability as it's the FP where it makes sense, however, I definitely see the point @theprash is making and this case looks a bit "forced."

I tried to be very dogmatic throughout my own implementation of these exercises only using immutable data, but I caved for this one. A doubly-linked list isn't naturally a FP structure and I'm sure the creation of this exercise was done without FP in mind.

It looks like no one that has solved this problem so far has done it without using mutable state, so I'm not against modifying this to use mutable state. That change should also be coupled with an explicit call out in the description that this exercise doesn't follow FP's immutable style.

[rmunn]

The README asks you to implement a doubly-linked list, but in actual fact what they're asking you to implement is a deque. Which is usually implemented with a doubly-linked list in imperative languages, but there's a perfectly good way to implement a deque without mutation. See my second iteration of this exercise, where the only reason I used mutation is because that's what the test suite required me to do at the time. (The test suite has since been changed to not require mutation, so that that implementation would no longer compile or pass). What I wanted to do (and could do now) is replace those tail <- item :: tail mutations with something like { deque with tail = item::deque.tail }.

I forget: does the README have to be identical for all tracks of the exercise? Or can the F# version (and the version for any other FP languages) of the README change it just enough so that it doesn't specifically require a doubly-linked list, and instead allows you to solve it with any deque implementation, including a purely-functional immutable one?

[ErikSchierboom]

As far as I know, it is not possible to override the default README, but what we can do is add #234. Maybe we should include an extra hint stating that you just need to implement a deque?

[robkeim]

@rmunn while your second iteration is very clean I'm not sure it complies with the README which states:

Implement a Node to hold a value and pointers to the next and previous nodes`

IMO, this exercise was intended to avoid using higher level constructs of the language such as lists and the cons operator, and dig in under the hood and manage nodes and "pointers" to give you a deeper understanding of how a double linked list (deque) data structure is implemented.

That's at least the way I interpreted it, but it makes more sense in languages like C++ where you're managing your memory and dealing with pointers on a regular basis. This exercise reminded me of one of my first programming homework assignments in school :)

[rmunn]

That's why it was my second iteration. My first iteration complied with what the README wanted in every detail. Then I wrote the second iteration to demonstrate the way it should have been implemented -- except for the mutability that I couldn't get away from because (at the time) the unit tests demanded it.

[theprash]

I vote against having a README that contradicts the tests and/or hints. There are already other examples of this and it's just confusing!

So far it seems like the sensible options are:

1. Embrace mutation for this exercise.
2. Remove this exercise from the F# track and maybe create a new one for a deque.

@rmunn

The README asks you to implement a doubly-linked list, but in actual fact what they're asking you to implement is a deque.

That seems like your interpretation based on your past experience. I had never heard of a deque, but if you think it would be a better exercise then it should be a new one that makes it explicit.

[ErikSchierboom]

Perhaps then this is good exercise to allow people to test their F# mutability skills?

[robkeim]

+1 for embracing mutation on this exercise

[ErikSchierboom]

Okay, then let's modify this exercise to use mutation. We should definitely add a hints file explaining that mutation is not something you usually want to use when doing F#, but that it does has its place.

[theprash]

I should be able to submit a PR tomorrow.

[ErikSchierboom]

Closed with #248.