Replace Difference Of Squares and Grains on the core track

[sshine]

After a discussion on #track-haskell @ Slack, I'm proposing here that we move both Difference Of Squares and Grains away from the core track and replace these two last spots with other exercises.

A short argument is that they don't provide a lot of opportunities to teach Haskell idioms or data types. Finding explicit formula instead of recursive formula is more of a mathy exercise. While I like Grains, I don't think it deserves to be the last core exercise.

In coming up with alternatives, not a lot of exercises have been suggested: Bracket Push, Nucleotide Count. We could revise the order if the ones we come up with are not ideal to place at the end of the track. In fact, I might like to suggest that either way.

Finally, this might be a good opportunity to port new exercises, since we can do it in such a way that they apply to the track. I said on Slack that I miss the following things from the core track: Trees (like Binary Search Tree), Maps (like Nucleotide Count), higher-order functions (that aren't list combinators), Either (or a variant that accumulates errors), Monoid, parsing, list comprehensions, state monads, applicative functors, QuickCheck (properties and generators).

So how about we find / come up with exercises that cover things we haven't covered already, and then think about the order on the core track?

[petertseng]

If exercism/exercism#4110 is an Exercism-wide policy, we need to remove not only difference-of-squares but also sum-of-multiples and collatz-conjecture, but I suppose I can defer their removals until after there's a replacement for... whatever role in the sequence they play.

I must admit I'm better at thinking of exercises that match a given topic rather than deciding what topics should go in the core curriculum. Let's see what we came up with.

Trees

Don't think we have a good one right now. POV is about them, but too much for an intro. binary-search-tree does exist but that's making students implement their own rather than a situation where we can use trees

Maps

maybe etl can be good here?

higher-order functions (that aren't list combinators)

there is the fact that accumulate (poorly named!) and strain have students implement them. I'm hard pressed to find an exercise that would suggest their use though since there are so many ways to solve a given exercise.

Either

nucleotide-count or largest-series-product perhaps? for this one there are already a few exercises that have Either so mostly it's grepping the repo for it and picking one

Monoid

Eh there was once mention of that in binary-search tree #59 , but I'm not convinced it's strong enough to build the connectoin

parsing

wordy perhaps. sgf-parsing has it in the name. poker and alphametics have a bit of it but a bit limited. Even bracket-push can be done as a parser, but I haven't seen anyone do that for a long time. I'm not sure if https://exercism.io/tracks/ocaml/exercises/bracket-push/solutions/67c607f6684646c4a5737a3b0fa289b7 makes it obvious that what's going on is parsing

list comprehensions

seems tough since I can't predict how a student will choose to implement, but perhaps pythagorean-triplets is a possibility

state monads

robot-name perhaps, since #727. I also used runST{U,}Array in sieve and sublist but I don't think that's usual

applicative functors

all I have for this one is that I used a liftA2 in my minesweeper, but again no guarantee that anyone will do the same

QuickCheck (properties and generators).

perhaps allergies fits the bill now

[sshine]

Why would we need to remove all of them? Because they're mathy?

(#727: Changing robot-name to use StateT, not sure what the principle is.)

Sum Of Multiples teaches both about Data.Set and how to generate results efficiently. It covers a piece of standard library, using sets probably forces the student to re-structure their helper functions, it teaches about Foldable (you can sum a set), and while there are explicit formula, you don't have to cover them to get a lot out of the exercise.

Similarly for Collatz Conjecture, there's a lot of interesting learning points that hardly any student gets right the first time. Use guards, an accumulating argument isn't more efficient, avoid explicit recursion with iterate, naming things. I'm not in love with it, but I don't understand why it must go.

---

Yes, ETL is another good candidate. It's on the OCaml core track.

For trees I'd like to see if we can port a new exercise. There are so many interesting kinds of trees.

We could also change the error handling of RNA Transcription to use Either Char, since this exercise is a bit too easy and Collatz Conjecture has covered Maybe before it. The change would be minimal.

For list comprehensions I remember an exercise at university where for a morse string ".--.--" you had to generate all possible decodings of it. I remember that the list comprehension-based solution was the most elegant. (Encode and decode being inverses is also an easy property to test.) Probably not ideal for the core track, since we don't want people to get stuck.

For QuickCheck we could also extend RNA Transcription since it is very easy to create positive and negative generators for input to this function. Making generators becomes very difficult once your data types are recursive, so it'd be nice to start off with basics.

[petertseng]

Huh. How did I make such an obvious error. I meant to link to exercism/exercism#4110 for citing the removal of sum-of-multiples and collatz-conjecture. I'll have to edit my post.

[petertseng]

I've acquired an answer on whether it's required to remove those sum-of-multiples and collatz-conjecture:

It's not required. exercism/exercism#4110 (comment) says we are free to do as we wish.

Great, then let's continue to focus on what we should add to replace difference-of-squares and grains.

[petertseng]

For trees I'd like to see if we can port a new exercise. There are so many interesting kinds of trees.

I'm not sure I know of an existing suitable exercise off the top of my head, but there's always the possibility of me being proven wrong. But in case I wasn't wrong, let's also bring forth the possibility of creating a new exercise in problem-specifications OR creating a track-specific exercise.

[sshine]

For a new exercise about trees, here are tree ideas:

(one) Port tree-building from F#.
(two) Create a new exercise based on game trees (exercism/problem-specifications#1388)
(tree) Create a new exercise based on generating random dungeons.

[petertseng]

(one) Port tree-building from F#.

Have you thoughts on whether it should stay as a refactoring exercise (as https://github.com/exercism/problem-specifications/blob/master/exercises/tree-building/description.md specifies it should be) versus not (implement from scratch)?

So how about we find / come up with exercises that cover things we haven't covered already, and then think about the order on the core track?

I'd also like to bring up the possibility of doing some of this piecemeal.

For example, if it is already possible to agree on an order in which the concepts should be presented on the core track, then we can immediately add any concepts for which an appropriate exercise has been identified.

If that is not possible, perhaps consider a case where we nevertheless have identified some but not all exercises that should be added. If we are able to assume adding an exercise doesn't change the desired relative ordering of any other pair of exercises, then we can add whatever exercises we've identified.
(I could state that more formally like "given that exercise E1 is before E2, there is no exercise E3 that we can add that would cause us to want to put E2 before E1" but I'm sort of hoping the plain description was sufficient)

Assuming that it's not too disturbing to students and mentors to be changing the core exercises iteratively rather than all in one go.

[sshine]

Have you thoughts on whether [tree-building] should stay as a refactoring exercise

Yes, I'd prefer if it weren't, but it seems that the consensus in exercism/problem-specifications#1174 is against. I like the idea of refactoring exercises in Haskell, but I don't know if I think this one is particularly well-suited. Let's discuss refactoring exercises in another issue and pick another exercise as the first tree exercise. (The theme, however, is very nostalgic to me, since building a forum with nested comments is the first time I solved a problem that involved a recursive data structure as a kid.)

Because the random dungeon idea 1) depends on a previous dice-rolling exercise being made first, and 2) isn't just a tree exercise, but also a random generator exercise, I'd favor game trees or a similar tree-based exercise without constraints (either ported or new).

[sshine]

Consider exercises that teach the use of monads and do-notation beyond error handling and IO (suggested by @petertseng in #782).

[sshine]

Closed issue in favor of #798.

The discussion in this issue are worth to bring into #798.