Total storm in teacup! Jose is a very interesting, clever, and thoughtful person. I was just jotting down (several weeks later) my probably-inaccurate recollection of a conversation over a beer. The problem spec I referred to is the best reference. Stick to that!
2 Likes
mapAccumL can be implemented with an actual accumulating parameter, with the same interface. I just assume it’ll be less efficient (benchmarks?) without the StateT.
If any use of local state can be represented by StateT, then any use of local state can be represented by accumulating parameters. Then even without State monad, every use of imperative code with local state (mainstream definition of pure) can be represented by “pure” closures.
I actually posted the origin of the challenge to show that it is a typical problem imposed by a less than ideal 
interface to some program that you have to work around. Because you can’t change it now for whatever reason, be it that it’s some 3rd party e-learning app/service/… or you just don’t have the time.
And I can guarantee you that everybody of us has either already produced some similar (or worse) code or will do so in the future. I certainly have.
3 Likes
I imagine it would be exactly the same. It should desugar to almost identical code, becoming identical after optimization.
Why not foldr?
data Ev course lesson
= NewCourse Bool (Int -> [lesson] -> course)
| NewLesson (Int -> lesson)
-- probably a very simple call to `concatMap` depending on your datatype
fromCourses :: YourInput -> [Ev YourCourseType YourLessonType]
fromCourses = undefined
makeCourses :: [Ev course lesson] -> [course]
makeCourses xs = foldr go (\_ _ c ls -> c (ls [])) xs 1 1 (const id) id []
where
go ev k !courseIx !lessonIx makeCourse lessons = case ev of
NewLesson l ->
k courseIx (lessonIx + 1) makeCourse (lessons . (l lessonIx:))
NewCourse p c ->
makeCourse (lessons []) .
k (courseIx + 1) (if p then 1 else lessonIx) (\ls -> (c courseIx ls:)) id
whilst this solution is meant as a joke rather than real code, I don’t think it’s a particularly absurd solution. Turn your input data into some sort of builder, and then write something to run that builder.
4 Likes
Golfed version using Dynamic and with a newtype for Object over HashMap Text Dynamic:
{-# LANGUAGE OverloadedStrings #-}
import qualified Data.HashMap.Strict as HM
import Data.HashMap.Strict ((!))
import Data.Text (Text)
import Data.Dynamic
import Data.Bifunctor (second)
import Data.Maybe (fromJust)
import Data.Vector (Vector)
import Data.Traversable (mapAccumL)
newtype Object = MkObject {unObj :: HM.HashMap Text Dynamic}
hiJose :: V.Vector Object -> V.Vector Object
hiJose = snd . mapAccumL go (1 :: Int)
where
go count (MkObject obj) =
second (\lessons -> MkObject $ HM.insert "lessons" (toDyn lessons) obj)
. mapAccumL numberLessons
(if flip fromDyn False $ obj ! "reset_lesson_position"
then 1 else count) . fromJust . fromDynamic $ obj ! "lessons"
where
numberLessons subCount vecObj =
( subCount + 1, toDyn . MkObject
. HM.insert "position" (toDyn count) . unObj . fromJust $ fromDynamic vecObj )
Yes, Map.(!) and fromJust is partial, but it sort of highlights in how the original implementations a malformed data input can blow you up.
2 Likes
Some problems require imperative thinking, and in most cases imperative solution is often easier. Seems like this is one instance of the general circumstances.
1 Like
It’s just mapAccumLs instead of for loops, tbh. (Did you catch the thread mentioning that higher order functions are replacements for for loops?)
What makes this actually hard is getting the correct data structure down (even the lazy “let’s define it as an HashMap Text Dynamic” becomes painful when you consider the type-tetris, and the fromJust annoys me).
1 Like
“Maybe storm in a teacup” was meant to say that maybe Jose never claimed that this problem was more challenging for functional languages, is all. Since I don’t know what he said, I have no clue. Besides I have not understood why this problem might be more difficult for functional languages, but that’s on me for not understanding.
Hi everyone, I am José Valim, who brought this topic to Simon. 
For more context, the problem was presented to me by someone who was familiar with an imperative language and was attempting to port an existing imperative application to Elixir, which is a functional language. I did not design it but I did write the spec down, as it was currently defined. If the problem description sounds utterly imperative, it was because it was made by someone who “thinks imperatively”.
Therefore, I would ask you to think about how you would explain the solution to someone who is just beginning their functional programming journey (after several years of writing imperative code!).
I am quite familiar with mapAccumL. That seems to be the “go-to” answer for other functional languages in the repository and how I would solve it in Elixir too!
For clarity, Elixir is functional and its data structures are immutable. So I wouldn’t be expecting anyone to be solving this problem in Elixir with mutability either.
I asked Simon’s opinion on a private conversation, legitimately interested on his input, and I did give him permission to share this problem with others (which he kindly asked). I am also not the person linked in the HN comments above.
While I do believe the Python solution is more accessible (to my personal interpretation of accessible), I don’t think that my opinion is relevant at all. I don’t claim it openly in events nor do I claim it to be universally true. Nor do I have a goal of pushing imperative solutions, although I am quite interested in learning whenever possible how to ease the migration from an imperative to functional mindset, and that includes helping users tackle “artificial problems”.
It is disappointing you chose to inaccurately portray both my intentions and my claims instead of engaging with the problem.
To everyone else, thank you for posting your solutions, I am sure I will learn something new.
29 Likes
Thanks for the clarification, I think your description of the situation implies something that’s very useful, and I think I’m personally non-plussed that I can’t get a solution more concise than the Python.
I’ve made a hobby of translating Python code into Haskell, and in my experience, Haskell is hard-pressed when it comes to imperative / effectful code (due to lacking early return without resorting to certain effect types or exceptions). It usually pulls ahead when it comes to functional / effectless code, however. Thus, because this problem is fundamentally effect-free, it’s annoying that it’s hard to deliver a clean, functional solution that can beat the Python.
2 Likes
For what is worth, I think it is fair game to rewrite the data structures to proper Haskell data structures instead of using the generic JSON ones. This could be, in itself, a good example of better modelling your problem/domain with types.
It’s not a question of “Haskell data structures”: it’s a question of an appropriate data structure for the application requirements. That could/should be equally expressible in JSON or any other data description formalism, including Haskell data types.
-
This is not a ‘key-value data structure’ in any sense. That wording appears only on your (José’s) github description, not the HN discussion. Why?
-
mapAccumLis indeed a nice higher-order function for hiding implementation ugliness:
[
mapAccumL] passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.
- What ugliness? “left to right” ugliness. I really don’t see that just because an elegant solution can be expressed in Haskell, that makes the “left to right” solution somehow not imperative. I get it that I’m quibbling over semantics.
- A
Traversableis not a random-access nor key-value access style of data structure. For example imagine trying to insert an extralessoninto the middle of the structure: we have to bump up thepositionof all the followinglessons, including crossing into the nexttitlegrouping to at least check if it hasreset_lesson_position = True; ifFalsecarry on bumping up – possibly across many followingtitlegroupings.
1 Like
Here’s a different question, what’s the data structure for? I’m sort of the village idiot here; I don’t have enough experience to guess out the broader problem for which you’d design the data structure.
Excellent question! And not at all a ‘dumb question’. Perhaps …
- A data structure for showing off the power of
mapAccumL. - A data structure for showing what can go wrong when you don’t capture the full requirements at first.
- A data structure that can’t possibly be a key-value structure.
- A data structure to demonstrate the limits of “left to right” thinking. (Suppose for example the
lessons are to be numbered from 1 starting at the end, as a countdown to when the learner has completed the topic area. That should be easy to do with a key-value data structure.)
1 Like
This discussion reminds me of back in my first year I went to the university of applied sciences. I was learning about designing systems, and one of the points teachers pressed on, was that the programmer is tasked with making a translation between what stakeholders want, and the actual design of the program. What stakeholders (typically non-programmers) say, can often be directly translated to code, and that is generally not the quick solution one should go for.
This discussion looks similar, except instead of stakeholders for a project, we have imperative programmers wanting to translate an implementation. I think an interesting question here is: how does one get to a translation? I think the best start is to ask some questions:
- What are these sections and lessons really? Book things? Lecture things? What is the real relation between them? Can lessons be shared between sections?
- What does it mean for a number to be added to the title? I don’t suppose that number is a fundamental aspect of that title. Is it for representing a table of contents(TOC) instead? Oh hold on, a TOC? That comes with more possible features, maybe we want to add the page number of where the section/lesson starts.
These questions are not specific to imperative or functional languages, though the answers might be coloured by the language of choice. Teaching functional programming to an imperative programmer means going back to the drawing board. Asking these questions is how I would personally go at it.
What’s wrong with resorting to the effect types or exceptions?
1 Like
As I mentioned, I am presenting the problem as it was presented to me. Plus this topic came up as part of a longer conversation, which made me recall the repository and the discussions that came from it. It is not something I am actively working but I thought I would get Simon’s opinion too (the repository was archived during all this time, except for a commit I pushed yesterday with one line of additional background).
In my opinion, it is completely fine to say “don’t do it”, “remodel your problem”, etc. Heck, it is even fine to criticize the spec as a poor simplification of the problem. However, extrapolating a brief context of a conversation you were not a part of to claims that I have an agenda, lack critical thinking, etc is a disheartening attempt to poison the well instead of engaging constructively. I am not interested in this conversation or in explaining my intentions a third time, so I won’t reply further to this sub-thread.
20 Likes
If I remember correctly (it has been a while), it was a sidebar with numbered links to lessons on an online video course. The “reset_lessons” is not an actual attribute on the data but a simplification of other characteristics which would reset the counter. A section has many lessons and the lessons are not shared.
The original author was able to tackle most of the problem, including other TOC-like features, but they struggled with numbering the sessions. At the time, I believe we did discuss solutions with the author using recursion and using Elixir’s equivalent to mapAccumL but they were both described as “unclear”. So I decided to summarize the sub-problem and collect solutions from different languages as a way to see how people would think around the problem (and potentially as a search for different functional solutions).
Apologies if that’s still unclear but it is the best I can recall so far.
1 Like
Thanks @FPtje, that’s a good chain of questions to stimulate a more disciplined and requirements-oriented outcome. (But I’d have to challenge your “can often be directly translated to code”: stakeholders are like the blindfolded people each trying to make sense of a different part of an elephant – they have only a vague idea how the bits connect together.)
Also I hope teachers emphasise the separation-of-duties between stating requirements vs the data model vs the program code. Ideally even when there’s staff equally competent in each discipline, assign different people to each role on a given project, to force each to make explicit their assumptions/guesses and avoid ‘tunnel thinking’. I really don’t like sweeping it all under the responsibility of ‘programmers’.
- I think we don’t have to probe too deeply into
lesson: it’s atomic for our purposes; it has aname. We want to give it a number for human-understandable purposes – see below. - I’m going to avoid the term “section” because that’s too vague; and seems to be used to mean different things. (I’m also puzzled why the very first
"Getting started"section has"reset_lesson_position": false. Doesn’t the very first (thing) want to say it’s a start point?) -
lessons appear in sequences, I guess/and from my experience in education because knowledge-gain works by building on earlier knowledge.
What seems to be going on (again I’m guessing/this needs confirming with stakeholders) is that some sequences-of-lessons build on earlier sequences-of-lessons. Whereas once the student has built up a sufficient foundation, later sequences-of-lessons can be taken in any relative ordering. This is known in education as ‘prerequisites’. Critically, it’s an attribute of a later sequence-of-lessons to point backwards to its prerequisite sequence(s)-of-lesson(s).
Now there would be a challenge to sift out imperative/sequential vs (lazy) functional approaches! At least validate the JSON to make sure the prerequisite(s) for a sequence-of-lessons does appear earlier in the file.
- In the example JSON, I imagine once the learner gets past “Basic operator”, they can opt to go on to either the “Mutability; Immutability” sequence-of-lessons, or the (making something up) “Function definition” sequence-of-lessons without either being a prerequisite.
I agree (but as you say we’re supposing/guessing). It’s for human readers of a coursebook to navigate/customise their learning. The JSON (if we take that as a database) knows perfectly well how to navigate a sequential file/it doesn’t need no numbering.
Yesss! Now we’re getting a decent programming challenge: output the TOC with page numbers at the start of the display, having by then numbered the lessons-within-sequence and each sequence-of-lessons.
Do we need something meeting the purpose of the reset_lesson_position flag? I’d say:
- for an advanced design challenge: no. Number afresh if the
prerequisite(s) for this sequence-of-lessons does not include the immediately preceding sequence-of-lessons.
or there’s a later sequence-of-lessons that branches off from somewhere earlier, jumping over me. [**] - for a newbie to FP: yes. There’s to be an extra layer of grouping in the JSON: outer-group
"Basics"is to include inner-groups"Getting started", "Basic operator". Next outer-group"Advanced topics"(with prerequisite"Basics") has a single inner-group"Mutating", with a single sequence-of-lessons (2 of). (And we need some more data in the example to help see how this structure works.)
[**] Hmm I’m not explaining that very well. An example would help: "Function definition" branches off from prerequisite "Basics", jumping over the “Mutability; Immutability” lessons.