I think the most Haskell-brained thing in every programming thought experiment is to see a specification and immediately start building a better data structure to solve the problem rather than submit to a poor model.
From the specification, you get a (flat) list of lessons and must produce a collection of sections, each of which contains a collection of lessons. The desire in the end is to render a table of contents with sections numbered from 1, containing lessons numbered from 1. The odd boolean field is how you know it’s time to create a new section.
Yes, I understood this part. What I didn’t understand has been why you would want to do that.
But now I understand that a course can have more than one section and this “rest_bla” marks the beginning of a new course. Which does make even less sense in my opinion
I think the few submissions mentioned above suggest nicely that the original challenge is a poor example of “harder / less elegant for functional languages”. I think a much better example would be to implement a (non-CLI) GUI easily portable to any major platform. This is pretty standard requirement in the industry, and one for which I think Haskell is in very bad shape in comparison to C++ / Rust / TypeScript / Python.
Of course, the difficulty comes almost entirely from the fact that portable GUI often requires turning to frameworks which are not Haskell-friendly or not even usable from Haskell, albeit through convoluted techniques. But I’d argue this doesn’t make it any less of a respectable problem for Haskell and functional languages in general.
Well, that’s real-life in the sense they got the design wrong, then tried to kludge it by programming round the mis-design. Not what I meant by “real-life”.
Nothing specific to “Haskell-brained”. Professional systems design says to fit the data structure to the business situation. Yes it’s often difficult to understand the whole business situation/you likely won’t get there at the first try. Doesn’t mean you should put up with a mis-fit.
So I’m not after a “better” data structure, just one that’s adequate to the business requirements.
What triggered my line of questions is trying to design a (relational) key-value store. The ‘example input’ contains no key-alike that would keep the nodes flagged reset_lesson_position in the sequenced position. So it’s not a key-value store; it’s a sequential store. Nothing necessarily wrong with that; just don’t mis-represent the problem.
Anyhoo Haskell has plenty of power to scan elegantly over sequential/JSON data.
Sure. We have input data as a sequence of sequences. This naturally leads to a Haskell representation as a List of Lists. Functional languages (since LISP) are excellent at elegantly iterating (recursing) over lists, carrying state as they go. Haskell is the world’s finest imperative programming language, after all.
And we have a dude Jose Valim who seems not to know how to describe programming problems or fit a data design to a requirement. Irrelevant.
Addit: in response to the comment just below
I wasn’t commenting on anybody’s program-writing. I’m commenting (as had several others before me [**]) on the statement of requirements; the data model; the design process by which a requirement uncovered late in the development wasn’t reflected back into the data model. Development isn’t all programming – indeed as I expect we’ve all experienced – programming alone can’t rescue a design that’s a poor fit to the use-case. (And the elegant Haskell programs shown here can only be elegant because the use-case isn’t a key-value store, contra the claims in the design doco.)
[**] Indeed all the criticisms here had already been made 2½ years ago in the YCombinator discussions that @ReleaseCandidate linked to. Including disagreeing with Jose’s claim that @simonpj’s intro repeats “an imperative solution just seems easier and more diret [sic] than a purely functional one”. In particular:
… when you’re stuck with a poorly defined data structure, …
The whole problem seems to be bizarrely defined when it comes to data structures.
I’m not sure the problem reflect anything, …
IMO The problem is poorly defined. Data structures should avoid control flow instructions like “reset_lesson_position”
The author is aware of the fact that mutability makes this kind of problem easier
Not clear from the spec that mutating rather than building a fresh output stream is required. (In situ mutating is what the example Python script seems to be doing – including inserting an extra tagged value.) But to suggest mutability means the input must be some sort of key-value store, not tackled as sequential JSON-to-fresh-JSON. I don’t see how the input JSON as given could represent contents of a key-value store. (There’s no keys.)
So why after all that feedback 2½ years ago is O.P. still at programming conferences hawking this as a meaningful exercise, and making claims that have been discredited about imperative solutions?
@AntC2 Let’s accept that there are people with different views on how to write programs and keep our criticism constructive with objective arguments instead of just saying other people are incompetent.
Edit: the comment this was referring to has now been edited.
Yes it is contrived but it’s fun to see how concise you can get it. mapAccumL was a good tip:
{-# LANGUAGE
DuplicateRecordFields
, RecordWildCards
#-}
module Lib where
import Data.Text (Text)
import Data.List (mapAccumL)
import GHC.Generics
import Data.Aeson
data Chapter = Chapter {
title :: Text
, reset_lesson_position :: Bool
, lessons :: [Lesson]
, position :: Maybe Int
} deriving (Generic)
instance FromJSON Chapter
instance ToJSON Chapter
data Lesson = Lesson {
name :: Text
, position :: Maybe Int
} deriving (Generic)
instance FromJSON Lesson
instance ToJSON Lesson
book :: [Chapter] -> [Chapter]
book = snd . mapAccumL fo (1,1)
where
fo :: (Int, Int) -> Chapter -> ((Int, Int) , Chapter)
fo (p1, p2) c =
let p3 = if reset_lesson_position c then 1 else p2
in ( (p1 + 1, p3 + (length . lessons $ c))
, c { position = Just p1
, lessons = lo p3 (lessons c)
}
)
lo :: Int -> [Lesson] -> [Lesson]
lo p = snd . mapAccumL no p
no :: Int -> Lesson -> (Int, Lesson)
no p l = (p + 1, l { position = Just p })
What I am wondering about is what exactly the creator of Elixir said or claimed. Maybe @simonpj can reference the actual words of his statement, so that we understand what he felt was a daunting task for functional languages? Perhaps all this is a storm in a teacup because this person never intended to “defy” functional languages in the first place?
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!
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.
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.
Some problems require imperative thinking, and in most cases imperative solution is often easier. Seems like this is one instance of the general circumstances.
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).
“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.
I am quite familiar with