← Back to context

Comment by kamray23

4 years ago

Yeah, I'd much rather have something like

  congruence_classes m l = map (\x -> ((x ==) . (`mod` m)) l) [0..m-1]

than

  def congruence_classes(m, l):
      sets = []
      for i in range(m):
          sets += [[]]
      for v in l:
          sets[v % m] += [v]
      return sets

For-in is very neat and nice but it still takes two loops and mutation to get there. Simple things are sometimes better as one-line maps. Provability is higher on functional maps too.

Same one-liner in (slightly uglier) Python:

  def congruent_sets(m, l):
    return list(map(lambda x: list(filter(lambda v: v % m == x, l)), range(m)))

11 comments

kamray23

Reply
gjulianm  4 years ago

The one liner is far less readable and under the hood it actually is worse: for each value in [0, m] you're iterating l and filtering it, so it's a O(n^2) code now instead of O(n). That mistake would be far easier to notice if you had written the exact same algorithm with loops: one would see a loop inside a loop and O(n^2) alarms should be ringing already.

Ironically, it's a great example of why readability is so much more important than conciseness and one liners.

  • verinus  4 years ago

    I agree and despite beeing a fan (kind of a convert from OO) of FP I am often wondering about readability of FP code.

    One idea I have is, that often FP code is not modularized and violates the SOLID principle in doing several things in one line.

    there are seldom named subfunctions where the name describe the purpose of the functions- take lamdas as an example: I have to parse the lamda code to learn what it does. Even simple filtering might be improved (kinda C#):

    var e = l.Filter(e => e.StartsWith("Comment"));

    vs.

    var e = l.Filter(ElementIsAComment);

    or even using an extension method:

    var e = l.FindComments();

    sorry I could not come up with a better example- I hope you get my point...

  • kamray23  4 years ago

    True, it is computationally worse, though it's O(nm) so applying m at compile time to form a practical use as I used it will turn it into to O(n) in practice.

    But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.

    I did consider the second one to also take quadratic time though. I forgot that in python getting list elements by index is O(1) instead of O(n) which is what I'm personally used to with lists.

    It's also true that you can replace the filter with

      [ v | v <- l, v `mod` m == x ]

    but that's not as much fun as

    (x ==) . (`mod` m)

    I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.

    • ummonk  4 years ago

      "I forgot that in python getting list elements by index is O(1) instead of O(n) which is what I'm personally used to with lists."

      Have you considered that maybe this is a sign you're too deep into using impractical programming languages?

      Cleanness for immutable data structures aside, linked list are a very poor way to store data given the way computer architectures are designed.

      1 reply →

    • gjulianm  4 years ago

      > True, it is computationally worse, though it's O(nm) so applying m at compile time to form a practical use as I used it will turn it into to O(n) in practice.

      Even applying it at compile time, it's still O(nm). You have to compute 'v mod m' for each possible value of v and m.

      > But that much is immediately obvious since it's mapping a filter, that is, has a loop within a loop.

      It's not immediately obvious because you have to parse the calls and see exactly where is the filter and the map.

          map(lambda x: do_some_things(x, another_param), filter(lambda x: filter_things(x), lst))
    map(lambda x: do_some_things(x, filter(lambda y: filter_things(x, y), another_list)), range(m))

      versus

          retval = []
    for x in lst:
       if not filter_things(x):
          continue
       
       retval.append(do_some_things(x))

      and

         for x in lst:
      filtered = []

      for y in in another_list:
         if filter_things(x, y):
             filtered.append(y)

     retval.append(do_some_things(x, filtered))

      In the first case, you have to parse the parenthesis and arguments to see where exactly are the map and filter cals. In the second, you see a for with a second level of indentation.

      > I just love how it looks and it doesn't personally seem any less clear to me, maybe a bit more verbose.

      It doesn't seem any less clear to you because you're used to it. But think about the things you need to know apart from what a loop, map, filters and lambdas are:

      - What is (x ==). Is it a function that returns whether the argument is equal to x? - What is '.'. Function composition? Filter? - Same thing with `mod` m. What are the backticks for?

      Compare that with the amount of things you need to know with the Python code with for loops. For that complexity to pay off you need some benefits, and in this case you're only getting disadvantages.

      That's the whole point of this discussion. Production code needs to work, have enough performance for its purpose and be maintainable, those are the metrics that matter. Being smart, beautiful or concise are completely secondary, and focusing on them will make for worse code, and it's exactly what happened in this toy example.

ummonk  4 years ago

Why not just use a list comprehension?

  def congruent_sets(m, l):
    return [[v for v in l if v % m == i] for i in range(m)]

  • 988747  4 years ago

    Isn't that unnecessary quadratic algorithm (nested loops, m*l iterations, instead of m + l)?

    • ummonk  4 years ago

      Yes, but that's the case with all the functional approaches proposed.

      If Python were focused on functional programming it would have a utility function for this similar to itertools.groupby (but with indices in an array instead of keys in a dictionary).

      2 replies →