Beautiful functional programming

[AntC2]

@FPtje

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,

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’.

What are these sections and lessons really? … What is the real relation between them? Can lessons be shared between sections?

• I think we don’t have to probe too deeply into lesson: it’s atomic for our purposes; it has a name. 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 don’t suppose that number is a fundamental aspect of that title. Is it for representing a table of contents(TOC) instead?

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.

… a TOC? …, maybe we want to add the page number of where the section/lesson starts.

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.

[maxigit]

I think that the fact you feel the need to defend yourself actually shows that you don’t.
What has becomming interesting with this challenge is not the (clever) solutions with have been proposed but the excuses which have been found to defend the lack of a good solution.

To be fair, the problem is clear and the python solution is straight forward and actually easier to check for correctness that all solutions iproposed in this thread (even though I haven’t written any Python in 15 years).

So instead of accepting the fact that yes, in that particular case and for whatever reason python might be a better fit, we are blaming on the problem itself, it’s not fair it stated in a imperative way, it needs mutation and states all stuff Haskell is not great at. Well that’s the point : Haskell is not great at certain stulff, and other languages are better at it.

[maxigit]

I’m not sure rewritting a challenge is a way to answer it.

I would just point out that in a way we are all “expert beginner”, meaning “we don’t know what we don’t know” (even if we really are good at what we know), and they are contexts which we aren’t aware of : that doesn’t make them invalid. A program can be written to control a robot on Marsn or a embedded on a raspberry pi to control flashing LED saying “Happy Birthday” in morse on a T-shirt.
Both are valid programs with there own challenges (for the later one challenge can be : I have one hour left).

To come back to this “artificial” non-well formed problem of the sequence of lesson. I am actuall working on a similar project. I am at the moment making a “French History” poster to hang on my kitchen wall.
The poster is a time of french history, with all the kings and government. It is basically a table with the following columns “Dynasty”, “dates”, “Monarch”, “Comment”, with one (or more monarchs per row)… Nothing fancy, no need for Haskell there.
The problem is I already have a “English History” poster and I’m planning to put them side by side, and I am trying to get the date coincide as much as I can. This involve grouping (or not) different kings in the same row, in that case the name of all the kings are not in the “Monarch” column but a list in the “Column”.
I started by copying the list of french monarch on wikipedia into Excell only to realize it was too much fiddling for me.There is quite a lots of french king and modifying the “groups” is actually time consuming.
So I decided to do what I always do : solve problem with Haskell. I’m writting a Haskell program to generate an Html page (the poster) from a csv (the list of kings + meta information).
Now, to put some kings in the same group, instead of copying them in the same Excell cell), I just need to write “Yes” in the “Start Group” column in the csv.

So I can see some similarities there with the lesson challenge : my king groupings is a bit like the reset_lesson_position and the context might also have been similar: a throw away script of a presentation ( or not …).

The way I am doing it, is probably ugly, but it’s a one of program which I am not planning to release to the outside world nor ever use it for another poster. I probably won’t use the best data structure possible but I probably already have spend more time on it that it will actually save me.
More importantly, even if it’s an ugly disposable program, all chalenges I’m encountering doing it are genuine programming challenges and If I were to ask for help I wouldn’t need to justify my initial “bad” choices : that’s the context, period.

Some of the challenges come from Haskell itself and maybe Python would have been better fitted for the task.

[jaror]

I tried getting similar code to the Python solution with lenses, but I think I went too far:

data Section a b c = Section
  { _title :: String
  , _reset_lesson_position :: a
  , _section_position :: b
  , _lessons :: [Lesson c] }
data Lesson a = Lesson
  { _name :: String
  , _lesson_position :: a }
$(makeLenses ''Lesson)
$(makeLenses ''Section)

data SolveState = SolveState 
  { _section_counter :: Int
  , _lesson_counter :: Int }
$(makeLenses ''SolveState)

solve :: [Section Bool () ()] -> [Section () Int Int]
solve sections = (`evalState` SolveState 1 1) $
  for sections $
        reset_lesson_position        %%~ flip when (lesson_counter .= 1)
    >=> lessons.each.lesson_position %%~ const (lesson_counter <<+= 1)
    >=> section_position             %%~ const (section_counter <<+= 1)

[Liamzy]

Also, is mapAccumL actually strictly necessary?

I’m not too good with optics (and I suspect there might not be an optic for this), but how about:

annotate = concat . fmap lensZip . groupBy (\_ new -> not new.renumber) )
  where
    lensZip = undefined

Depending on how clear and concise you can get lensZip, you can potentially beat the Python.

Dumb in any strict / eager language, okay in Haskell because laziness means everything is a stream…

gah, out of time, need to try again later…

TBH, one problem with Haskell vs Python is that Haskell sort of wants to avoid lambdas, on the logic that they’re not declarative, and instead bind a name to the lambda then plug the name where you’d otherwise use the lambda.

That can get more verbose than Python, but I want to try an mapAccumL version using (>>>) (function composition in reverse order) and lambdas inlined, since it’s closer to Python with anonymous blocks.

[halogenandtoast]

I feel like this is a good candidate for runST

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RecordWildCards #-}

import Control.Monad (when)
import Control.Monad.ST
import Data.Aeson
import Data.STRef
import Data.Traversable (for)

newtype SectionList = SectionList [Section]

data Section = Section
    { title :: String
    , reset_lesson_position :: Bool
    , lessons :: [Lesson]
    }

instance ToJSON SectionList where
    toJSON (SectionList xs) = toJSON $ runST $ do
        lessonPos <- newSTRef 1

        for (zip [1 :: Int ..] xs) $ \(sectionPos, Section{..}) -> do
            when reset_lesson_position $ writeSTRef lessonPos 1

            lessons <- for lessons $ \Lesson{..} -> do
                pos <- readSTRef lessonPos
                modifySTRef lessonPos (+ 1)
                pure $ object ["name" .= name, "position" .= Number (fromIntegral pos)]

            pure $
                object
                    [ "title" .= title
                    , "reset_lesson_position" .= reset_lesson_position
                    , "lessons" .= toJSON lessons
                    , "position" .= Number (fromIntegral sectionPos)
                    ]

newtype Lesson = Lesson {name :: String}

sections :: SectionList
sections =
    SectionList
        [ Section
            { title = "Getting started"
            , reset_lesson_position = False
            , lessons =
                [ Lesson{name = "Welcome"}
                , Lesson{name = "Installation"}
                ]
            }
        , Section
            { title = "Basic operator"
            , reset_lesson_position = False
            , lessons =
                [ Lesson{name = "Addition / Subtraction"}
                , Lesson{name = "Multiplication / Division"}
                ]
            }
        , Section
            { title = "Advanced topics"
            , reset_lesson_position = True
            , lessons =
                [ Lesson{name = "Mutability"}
                , Lesson{name = "Immutability"}
                ]
            }
        ]

main :: IO ()
main = print $ encode sections

-- $> main

EDIT: While structurally not as “pretty” as the python code, I feel like it gets close in spirit.

[tristanC]

Thank you very much @josevalim for introducing this problem and for taking the time to join us in this thread, that’s very generous of you!

I am also interested in learning how to ease the migration from imperative to functional. The Python solution appears more accessible than the FP variants, but perhaps we could demonstrate that it is not so simple. In this example, I find it surprising that the lesson_counter assignment in the if scope override the parent scopes. This becomes even more surprising when this happens inside a function scope, see: Why am I getting an UnboundLocalError when the variable has a value?. Taking these scoping rules into consideration, then I am not so sure that the Python solution is really more accessible.

[Liamzy]

TBH, when you have SPJ forwarding something by Jose Valim, you’re likely to get a very interesting and informative thread.

This thread brings 5 things to mind:

• For schemes (Haskell recursion schemes applied to for loops)
• Insufficient power of optics / zip?
• Haskell foldr is literally just an implementation of for (re: Probie)
• Labeled gotos might still be a good idea / Walrus operators in Haskell
• Benchmarking against Python via “Impractical Python Programs” and “Big Book of Small Python Projects”

For Schemes

Recursion is equivalent in power to while, and higher-order functions can be seen as replacements for for-loops. The advantage of higher-order functions, or specialized syntax resembling for-loops, over for is roughly the same as the advantage of for, while, and function calls over the traditional goto. Goto is simply too powerful, and is not expressive enough to indicate the intent of its use. Likewise, for can be seen similarily as too powerful (Go, for instance, lacks while, and implements all looping via for), and more specialized higher-order functions (or extensions to the for expression syntax, in Elixir) might be a better way to do it; i.e, the specialized higher-order functions represent specific uses of for and convey intent better.

This implies For Schemes, as an analogue to Haskell’s recursion schemes, i.e, a way to taxonomize and analyze things people do with for. For functional languages, this is particularly useful in the sense that if someone coming in from an imperative language wants to reach for a for loop, there’s an existing functional alternative that achieves the same result. For imperative and more traditional languages, as long as there’s compiler / interpreter support, you get the effects of being more specific than a for loop without sacrificing performance, as with Javascript array methods.

Ideally, we should be able to get “for loop considered harmful” in the same way “goto is considered harmful”.

Insufficient power of optics / zip

I’m not sure if this has been done already, whether it’s possible, but if you go from the idea that “higher-order functions are a better replacement for for”, and we can’t do this easily with optics and zip (but can with mapAccumL in Haskell / map_reduce() in Elixir), it implies that we are missing a specialized higher-order function for this task.

If I understand correctly, this particular problem resulted in the addition of let to for expressions in Elixir (Introducing `for let` and `for reduce` - Official Proposals - Elixir Programming Language Forum ), presumably over map_reduce(). Likewise, if existing features in optics and the zip function is insufficient, it implies that we might need new functions to automate this simply.

Haskell foldr is just an implementation of for (Probie)

I guess this is old hat, but it should be emphasized more that everything anyone can do with for, anyone can do with Haskell foldr (although not necessarily foldl’ / reduce). reduce holds an accumulator, i.e, implicit state, updates the state, but cannot short-circuit, as lazy-right folds can. foldr is powerful enough to store state in an external accumulator, build a continuation pattern from the original data structure, then implement any recursive pattern necessary (i.e, map, mapAccumL, filter, foldl’, traverse, etc).

Labeled gotos might still be a good idea. / Walrus operators in Haskell

Here’s a certain declarative programming problem in Haskell. A certain declarative style in Haskell completely eschews the use of lambdas, considering them insufficiently declarative, and relegating them to where clauses. I.e, you end up with named blocks in Haskell; what you’d do in another language with a block, such as a loop, you name instead and render a function, hopefully making the code clearer.

However, if you compare it to the Python, this can actually make the code less clear, because in Python, you have immediate access to the block for viewing, whereas you’d have to scan to the where clause or let declaration in Haskell.

In Haskell, a potential solution might be an equivalent to a Walrus operator, i.e, -XLetLambda / -XLetWalrus, to provide immediate use after declare.

Right now, if we want to do this, we’d have to do let foo arg = arg in foo, which can be unnecessarily verbose. A solution might be a language extension to the syntax allowing foo\arg -> arg syntax, i.e, the lambda is immediately used after declaration. We can also extend this to foo\->3 syntax for variable declarations.

Conversely, for more traditional languages, you might wish for a hoisting macro, i.e, a block of code has the macro applied, and it is now hoisted to top level, providing a name for the block, as well as optionally allowing reuse by creating a function that takes arguments filling in out-of-scoped names.

Benchmarking against Python

Lastly, I think Haskell losing to Python in expressiveness is pretty bad, because if you check out Hutton’s “Programming in Haskell”, he makes the claim that Haskell can be 2-10 times shorter than C, whereas Python claims to be 2-5 times shorter than C. When you look at functional Python, the gap obviously narrows tremendously, but Python doesn’t support functional programming well at the implementation level, and Haskell’s syntax is optimized for functional programming.

But benchmarking against Python is useful, since Python is considered the gold standard as a combination of readability and expressiveness, and moreover, Python is pretty good when it comes to its overall ecosystem.

There are a few open Python books introducing a bunch of newbie projects, say: Impractical Python Projects ( GitHub - rlvaugh/Impractical_Python_Projects: Code & supporting files for chapters in book ) and The Big Book of Small Python Projects ( GitHub - asweigart/the-big-book-of-small-python-projects: The source code for the programs in "The Big Book of Small Python Projects" ). I’ve ported one from the latter myself ( New, Average, and Pragmatic: Translation of Vigenere Cipher from "The Big Book of Small Python Projects" into Haskell ), but the Python books present an opportunity to benchmark the ecosystem maturity in your own language, the expressiveness and maintainability of the language, and present a possible Rosetta stone for newbies to grasp and hang on to.

Projects where you end up being significantly more verbose than normal can present possible pain points that need to be resolved, and projects where there are no good corresponding libraries in your own language might highlight points for improvement.

[josevalim]

@tristanC

In this example, I find it surprising that the lesson_counter assignment in the if scope override the parent scopes

I agree. The Python solution looks accessible because it hides all of the mechanics of how state is passed around and in functional programming we prefer those mechanics to be explicit, for very valid reasons (which may make our code seem noisier to others?).

And thank you for sharing your article. I particularly enjoyed your choice of using different data types for the input and output to solve this problem, which I believe helps outline the functions are transforming the data (rather than mutating in place as in Python).

@Liamzy

I’m not sure if this has been done already, whether it’s possible, but if you go from the idea that “higher-order functions are a better replacement for for”, and we can’t do this easily with optics and zip (but can with mapAccumL in Haskell / map_reduce in Elixir), it implies that we are missing a specialized higher-order function for this task.

This is a very interesting thought and I wonder if a new operation would help. People with functional programming experience look at the problem and say “oh, that’s a mapAccumL”. The issue is that those new to functional programming won’t necessarily see/know that. So we would need to consider if/how someone new would also know the new operation.

Perhaps the answer is that this is an education issue and mastering many of the higher-order functions are part of the job, so learn them! But even this conclusion branches into your next topic: you could also use foldr to solve the problem and use it as a general replacement for several uses of for. Should we promote one over the other? Yes/no? When/why?

@Liamzy

If I understand correctly, this particular problem resulted in the addition of let to for expressions in Elixir

Those proposals were not accepted because the community did not agree on them. However, could this also be a possible exploration point for Haskell? What if Haskell comprehensions also allowed you to pass an accumulator between iterations, effectively becoming some sort of flatMapAccumL? How would that look like? Would that help? At least, that’s what I tried to address in that Elixir branch but did not succeed.

[Liamzy]

This is a very interesting thought and I wonder if a new operation would help. People with functional programming experience look at the problem and say “oh, that’s a mapAccumL”. The issue is that those new to functional programming won’t necessarily see/know that. So we would need to consider if/how someone new would also know the new operation.

Perhaps the answer is that this is an education issue and mastering many of the higher-order functions are part of the job, so learn them! But even this conclusion branches into your next topic: you could also use foldr to solve the problem and use it as a general replacement for several uses of for. Should we promote one over the other? Yes/no? When/why?

The interesting thing about Haskell is that it’s not that different from Elixir, but whereas Elixir is interpreted to BEAM or Erlang, Haskell is translated to Haskell Core on the first of a few IRs.

A Prelude or base library can actually be considered a sort of language on its own; you can use -XNoImplicitPrelude to disable everything and not even expose the primitives (not without imports or -XMagicHash), so much of what is the responsibility of a language designer or implementer elsewhere can be done in userland.

So we don’t need a full operation, just a library somewhere that ends up being used, or a proposal to CLC to add the function to base, whereas poor Javascripters can try to be functional all they want, but end up blowing themselves up with atrocious performance.

---

As for for and foldr, well, I’m told that like Haskell, Elixir also has mutable overrides based on BEAM and the message passing model? The point is, while they’re there, they’re supposed to be emergency options. STRef actually optimizes worse than accumulating parameter (3 times slower in my benchmarks over naive factorial) and use of State.Strict monad (which is a convenient interface abstracting accumulating parameter) + modify’.
Data.List.foldr, likewise, can space leak. It’s there if you need it, it’s more idiomatic than abusing STRef / IORef / other mutables. And, imo, it’s less ergonomic than for; to get it to store state, you have to get it to convert the data structure to a continuation, then apply it to an outside value.

And that’s what I think about for / foldr; it’s not preferred, but if you can’t think of another way to do it, it’s there for you.

---

I think the big problem here is that we need For Schemes, i.e, to understand what users are doing with for-loops, then figuring out how to solve their problems with syntax for comprehensions in Elixir and higher-order functions in Haskell.

Many people just point me to traverse / for in Data.Traversable, but you still have the goto problem; we are just using overrides willy-nilly, without understanding the reason for using the overrides and finding a better way to avoid using the override.

[tomjaguarpaw]

I must say I’m a bit surprised by the direction of this discussion. There are a few things that confuse me. Firstly, people seem to have a clear idea of a delineation between functional code and imperative code. What is it? I don’t know! It’s not clear to me that those two concepts are disjoint. Secondly, people seem to have the idea that imperative code is somehow “worse” than functional code. Why? I don’t know! To me Haskell is the world’s finest imperative programming language. I have no qualms about programming imperatively (only about programming with unrestrained effects). Thirdly, people seem to believe that Haskell can’t express the same ideas as the nice Python code. It can! Look below; it’s almost a direct translation of of the Python into the Haskell.

There are a couple of caveats in the translation. Firstly, the Haskell data structure is immutable, meaning that we have to explicitly replace the old one with the new one. That adds a couple of lines. Secondly, Haskell is pure, meaning that we have to get the counter in a separate step from using the lesson counter. That adds another couple of lines.

Often, writing in Haskell the same code that you would have written in Python is the right thing to do! I wish Haskellers would do so more.

sections' :: [Section Int]
sections' = flip evalState initialCounter $ do
  for sections $ \section -> do
    when (resetLessonPosition section) $
      lessonCounter .= 1

    lessons' <- for (lessons section) $ \lesson -> do
      lessonCounter' <- use lessonCounter
      let lesson' = lesson {lposition = lessonCounter'}
      lessonCounter %= (+ 1)
      pure lesson'

    sectionCounter' <- use sectionCounter
    let section' = section {sposition = sectionCounter', lessons = lessons'}
    sectionCounter %= (+ 1)

    pure section'

Full code: Solution to https://discourse.haskell.org/t/beautiful-functional-programming/7411 · GitHub

[rhendric]

@tomjaguarpaw

sections' :: [Section Int]
sections' = flip evalState initialCounter $ do
  for sections $ \section -> do
    when (resetLessonPosition section) $
      lessonCounter .= 1

    lessons' <- for (lessons section) $ \lesson -> do
      lessonCounter' <- use lessonCounter
      let lesson' = lesson {lposition = lessonCounter'}
      lessonCounter %= (+ 1)
      pure lesson'

    sectionCounter' <- use sectionCounter
    let section' = section {sposition = sectionCounter', lessons = lessons'}
    sectionCounter %= (+ 1)

    pure section'

Things I can only dream of: an -XRecordUpdateDo that would let someone write:

section { do
  lessons <- for (lessons section) $ \lesson -> do ...
  sposition <- use sectionCounter
}

as sugar for

do
  lessons' <- for (lessons section) $ \lesson -> do ...
  sposition' <- use sectionCounter
  pure section { lessons = lessons', sposition = sposition' }

[lazamar]

How about doing it without using any accumulator at all?
No folds, just map, filter and zip.

https://gist.github.com/lazamar/305e8808f8975258f6acea4d20fd3405

[Liamzy]

{-# LANGUAGE DeriveGeneric, OverloadedStrings #-}

import Data.Text (Text)
import Data.Traversable (mapAccumL)
import Data.List (groupBy)
import Control.Arrow ((>>>))

data SimplifiedData a
    = MkSimplifiedData
    { renumber :: Bool
    , lessons :: [a]
    } deriving (Functor, Foldable, Traversable, Show)
    
data Lesson = MkLesson {lessonName :: Text} deriving Show

data AnnotatedLesson = MkAnnotatedLesson Text Int deriving Show

annotate :: [SimplifiedData Lesson] -> [SimplifiedData AnnotatedLesson]
annotate = groupBy (\_ new -> not new.renumber)         -- Implements the boolean check via groupBy, chunking the
                                                        -- list by renumber boolean.
    >>> fmap ( (mapAccumL >>> mapAccumL)                -- fmaps into the list of list of Simplified data,
                                                        -- with a composition of mapAccumL, i.e, map_reduce()
                (\count MkLesson {lessonName} ->        -- The map_reduce composition takes a numbering function
                    (count + 1                          -- that takes the accumulator
                    , MkAnnotatedLesson lessonName count-- and applies it.
                    ) )                                           
                    1                                   -- The initial accumulator
                    >>> snd )                           -- Discards the accumulator.
    >>> concat                                          -- Merges the list of lists
                                                        -- into a list of SimplifiedData again.
                                                        
{- Version without comments or type annotation.
   Technically 1 word shorter than the Python.
   
annotate = groupBy (\_ new -> not new.renumber)
    >>> fmap ( (mapAccumL >>> mapAccumL)            
                                                    
                (\count MkLesson {lessonName} ->        
                    (count + 1                        
                    , MkAnnotatedLesson lessonName count
                    ) )                                           
                    1                             
                    >>> snd )                      
    >>> concat                                       
-}

{-

More idiomatically:

annotate = concat
    . fmap ( snd . (mapAccumL . mapAccumL)
            (\count MkLesson {lessonName} ->
                (count + 1
                , MkAnnotatedLesson lessonName count
                )
            )
            1 )
    . groupBy (\_ new -> not new.renumber)

-}
    
test = [ MkSimplifiedData False [MkLesson "Computer", MkLesson "Crash"]
       , MkSimplifiedData False [MkLesson "Foo", MkLesson "Bar"]
       , MkSimplifiedData True [MkLesson "Paper", MkLesson "Pencil"]
       , MkSimplifiedData False [MkLesson "Imperative", MkLesson "Functional"]
       ]

New mapAccumL version, that’s shorter than the Python, but not necessarily more readable. This was what I was trying to post earlier.

It also highlights my point about naming lambdas; i.e, we could remove all the lambdas, replace them with names declared in the where clause, but would it be more readable then?

@tomjaguarpaw:

Imperative vs functional isn’t clearly delineated, but there is stateful, explicit mutation on one end, implicit mutation or quasi-mutation via State / accumulating parameter, as well as what I’d consider to be a relative pure solution via zip + optics.

The idea is more, functional programming should pull ahead and be preferred for data transforms, potentially at the cost of being comprehensible for the uninitiated, but being more concise and bug resistant without mutation.

But I can easily imagine talking to your juniors (including someone like me) and explaining that this idiom and the higher-order function involved is obscure and that an imperative approach would be better for the codebase, and you’d probably be right.

---

As far as preferring the imperative approach goes, maybe, but I’d always stand by an imperative approach if the choice is between an imperative approach, nothing, or a clumsy functional approach. We should be seeking more elegant ways to do this functionally no matter what, because while imperative programming is relatively well-explored, functional programming, although we have base camps, evacuation helicopters, and so on, is not, and the promise is still more understandable (declarative) and maintainable code.

---

I think the fact that we’re having difficulty getting a functional approach to pull ahead of the imperative one on this problem is, at the very least, providing an interesting exercise and topic for exploration.

---

Finally, credit has to go to mniip for the composition of mapAccumLs as something I overhead on FP Discord. Perhaps I should have waited for him to implement? It turns out mapAccumL composes evenly, although a third mapAccumL isn’t helpful as it just ends up ignoring the groupBy.

[Nycticorax]

I like it! Concise and readable.

[nemo]

I think your implementation is my favourite one so far.

[tomjaguarpaw]

The use of groupBy is very cunning! I always assumed that the first argument to groupBy ought to be an equivalence relation, but maybe it’s fine for it to not be.

But your version doesn’t number the sections. If you add that feature it’s going to be longer than the Python

[tomjaguarpaw]

I like the grouping by approach! Unfortunately there is an issue with a couple of consequences. numberLessons essentially splits apart the structured data and then recovers the data by matching on title name. Firstly this is inefficient because annotated must be walked several times. Secondly this means the code is wrong if the same title appears more than once in a group. For example

  numberIt
    [ Section "One"   True  ["A", "B"]
    , Section "One"   False ["C", "D", "E"]
    , Section "Three" True  ["F", "G"]
    , Section "Four"  False []
    , Section "Five"  True  ["H"]
    ]

leads to the output

Numbered 0 ("One",[Numbered 0 "A",Numbered 1 "B",Numbered 2 "C",Numbered 3 "D",Numbered 4 "E"])
Numbered 1 ("One",[Numbered 0 "A",Numbered 1 "B",Numbered 2 "C",Numbered 3 "D",Numbered 4 "E"])
Numbered 2 ("Three",[Numbered 0 "F",Numbered 1 "G"])
Numbered 3 ("Four",[])
Numbered 4 ("Five",[Numbered 0 "H"])

Whilst neither of these may be a problem in practice I think they imply that the code is more subtle than it needs to be.

[tomjaguarpaw]

The grouping approach by @lazamar and @Liamzy made me realise that the stateful section counter in the Python can be removed by (in Python) enumerate or (in Haskell) zip [1..]. @halogenandtoast also used that approach, but I didn’t notice it at the time.

sections' :: [Section Int]
sections' = flip evalState initialCounter $ do
  for (zip [1..] sections) $ \(sectionCounter, section) -> do
    when (resetLessonPosition section) $
      lessonCounter .= 1

    lessons' <- for (lessons section) $ \lesson -> do
      position <- use lessonCounter
      lessonCounter %= (+ 1)
      pure (lesson {lposition = position})

    let section' = section {sposition = sectionCounter, lessons = lessons'}

    pure section'

Much nicer! I would say this is “less imperative” because it uses a smaller set of effects (i.e. a state of a smaller data type). I would say it’s “better” for that reason. I’m not sure I’d say it’s “more functional” though perhaps it’s is because the higer order function argument to the first for is doing “more” work. This is now very similar to @halogenandtoast’s version.

Full code versions: Revisions · Solution to https://discourse.haskell.org/t/beautiful-functional-programming/7411 · GitHub

[maxigit]

@tomjaguarpaw

people seem to have a clear idea of a delineation between functional code and imperative code. What is it?

I think we can make a clear delineation between code relying on a sequence on statement mutating a global state (machine code, assembly, C, tidying up ones bedroom) and others
It somehow mimic how the world works (and we are quite good at it) but it can be become quickly tricky to remember the current state (unlike in the real word) you can’t see it and have to imagite it.

It’s not a matter of bad or good, but by using a high-level programming language where everything is immutable by default you pretty much committed to not do “a sequence of statements mutating a global state” or at least avoid as much as possible.