Binning Haskell with DSA?

#1

I had a conversation with a gentleman who shall not be named (not Axman, someone else), who did TA on Haskell / OCaml courses.

We were talking about how the Racket community, including their Brown professor, feels that it’s stupid to teach recursion with Fibonacci (better done via binet / matrices) and factorial (better done with primeswing or hgmp), and how they prefer to teach recursion by introducing recursive data structures first, and using that as an example to teach recursive algorithms and how recursion can be superior to iteration.

To my surprise, he actually agreed with me, and was even more vociferous about how Fib and Factorial being horrible for teaching recursion. I broached a remark about how “it’s silly to teach recursion without teaching the [] data definition first”, and he went so far as to suggest that data structures be taught before recursion.

===

To academics, I’m curious. Has anyone ever tried to teach a DSA course using a combination of Haskell and C on the honors level? In theory, Haskell should be excellent for that; recursive algorithms are pretty trivial when it comes to Haskell, but we know how hard it is to teach Haskell. Ideally, I’d love to see a 2 semester course somewhere, along the lines of UChicago doing intro CS via Haskell, where Haskell and C are binned together with DSA.

The only problem, of course, is that Haskell has terrible OOP support, but I suppose you could always do the “teach OOP by implementing objects via C” approach that people used to do.

===

Sources:

https://htdp.org/2022-8-7/Book/

2 Likes
#2

Since it took me a second, in the context of this post DSA apparently means “Data Structures and Algorithms”

6 Likes
#3

Everything I’ve heard about teaching Haskell has been positive. The complaints start with library/cabal/etc…

Is that a problem?

2 Likes
#4

I’ve stated elsewhere that I don’t support the notion of Haskell ever having first-class OOP support.

However, Scheme is often used as a teaching language because it’s fully multi-paradigm; I think the logic with UChicago doing Scheme in intro comp sci and Haskell in Honors intro is that they already know OOP, whereas most programmers, amateur, UChicago students, or not, do not know FP.

1 Like
#5

What is wrong with haskell adopting OOP? Wouldn’t it make haskell more practical for general usage?

1 Like
#6

What is wrong with haskell adopting OOP? Wouldn’t it make haskell more practical for general usage?

OOP is a tool for some problem domain. You can have OOP in Haskell, it just not needed as much, given all the alternatives.

3 Likes
#7

I teach a language course rather than a data structure or algorithm course. Having said that, I don’t refrain from dumb factorial and fibonacci, but I make sure:

With dumb factorial I remark that it’s slow, there are easy way to be faster, sometimes I even include a URL for that.

With dumb fibonacci I include this joke.

I follow up with examples of actually meaningful recursions. As you agree, best done with basic algorithms on common recursive data structures, such as insertion sort for singly-linked lists, binary search tree operations.

3 Likes
#8

I’m no teacher, but yes using recursion for Fibonacci or factorial seems overkill when iteration is the usual way they’re explained, let alone the more natural way to think about them.

Recursion over data structures probably doesn’t need deep knowledge of data architectures. Nice examples in Haskell would be inserting into a binary ordered tree (and keeping it balanced – perhaps a red-black tree), or chopping a String into a list of words, or into substrings of ascending sequences.

Why would OOP support come into it?

1 Like
#9

The classic is Wirth’s Algorithms + Data Structures = Programs – very influential at the time I learnt programming, and inspired the Pascal language. You can see where Functional Programming’s data structures come from.

1 Like
#10

One thing I do wonder about is using Fibonacci to teach memoization in Haskell; like, the memoized fib, while still suboptimal compared to matrix-based or Binet-fib, is still relatively simple (use zipWith).

Fibonacci is the standard memoization example, though.

===

A question I’m floating is whether Haskell is fun for DSA in general; as in, you can do imperative algorithms with IORef / concurrency mutables and ST monad, you can do functional algorithms with just pure code.

One thing I encountered was that someone was teaching Haskell recursion with quadtrees, but somehow a ton of the students missed recursion in their DSA class and couldn’t grok it.

===

I’m not big on Haskell as a “pure”, in the vulgar sense, functional language; stuff like using accumulating parameters to simulate local variables makes sense in the same way Scheme in SICP taught recursion and iteration at the same time using accumulating parameters.

===

Lastly, re OOP, Scheme was used as a general purpose teaching language for a while simply because it was fully multi-paradigm. Haskell is functional by default, monadic by design, meaning that it supports both functional and imperative paradigms, and LogicT adds logic programming, but the poor OOP libs mean that it can’t be used as a full multi-paradigm GP teaching language, because you can’t introduce OOP as necessary.

Even though a lot of people coming in to Haskell hate OOP, it’s still a dominant paradigm that FRP cannot yet fully replace, and thus worth teaching. Also, the FP jobs space is terrible, so OOP is still useful because tons of kids are going to graduate and become Java or .NET devs.

2 Likes