Follow

Functional programming fans, a challenge:

Here are two problems I've needed to solve lately where I don't see any reasonable way to do them with your average set of basic functional tools and immutable data, and instead I've ended up having to write very procedural loops-and-mutable-arrays type of code.

That code is generally not very satisfying to look at, but I just don't know any other reasonable solution, so, I'd love to hear how you would solve these:

1. Given a list like: [(1, a), (2, a), (3, a), (4, b), (6, b), (9, c)], transform it into:

[([1, 2, 3], a), ([4, 6], b), ([9], c)]

2. Given a list of ranges like this: [(1, 3), (4, 8), (8, 10), (10, 12), (19, 21), (21, 23)], join adjacent ranges into:

[(1, 3), (4, 12), (19, 23)]

For this one, ordering and adjacency are important, so [(1, a), (2, b), (3, a)] would remain unchanged, for instance.

@WAHa_06x36 not exactly. First one is a grouping task, while the second task is a finding joining of range task.

And both of them can be solved by building a pre-processing immutable list/iterator with splicing by two elements at once and calculating things inside a tail-recursion :)

I will try solving them in #scala

Scala code 

Scala code (part 2) 

@WAHa_06x36

At a quick glance, they're all pretty straightforward problems for a catamorphism to solve.

@WAHa_06x36
1 is just folding into a map then transforming the map on the way out of the fold.

2 is trickier but it's a more restricted variant of what's sometimes called "the 2d skyline problem". A solution of that more general problem in Haskell is here: pykello.github.io/2015/12/hask

@endomain Can't just use a map for the first, since the point (as described in a later reply) is to take into account adjacency too: mastodon.social/@WAHa_06x36/10

@WAHa_06x36

That's not true for the example you have if you key by the second value in the tuple and then invert the map on the way out. The entire problem can be solved in linear time as per than example.

@WAHa_06x36
However if there are additional requirements not listed there then we could still do it in a map by tuning the keys and having a decision be made about adjacency.

If anything, that makes the problem easier now because we can do it by simply tracking one open interval instead of labeled intervals. We'd need only sort the initial tuple productwise, left to right and then it's a single pass. Since sorting is O(n), the process is still linear time.

@endomain Also, I think that's generalising much too far for the second, this problem is a lot simpler than that.

@WAHa_06x36

I think the approaches used there are simple, but yes the skyline problem is a much less constrained interval problem. I just wanted to give you a sense of how FP tackles those problems at a coarse level.

@endomain What I am looking for here is how FP solves a very simple problem, that has a very straightforward procedural solution, without becoming utterly esoteric and indecipherable.

So I kind of want the opposite.

@WAHa_06x36

One moment and I'll have time for the first one. That's quick.

But quick questions to get the edge cases:

What is the output (including "error: invalid input") of:

[(1,a),(19,b),(2,a),(20,b)]

[(2,a), (1,a)]

[(2,a),(2,b)]

[(1,a), (2,a), (2,a)]

@WAHa_06x36
ncry.pt/p/sLOn#asMI_D-rRYqH_2s

This is a working definition of what I perceive to be the requirements written as an executable haskell script. I have attempted to be as clear as possible to the point of omitting libraries I would normally use for performance (e.g., Sequence)

A lot of times FP folks are in the habit of slicing up functionality for later reuse. I deliberately did not do that here (hence mergeToInterval is one function returning a Maybe) in the style of python one-offers.

I'll do the other one later. I am, after all, stealing work time for this.

@WAHa_06x36

2nd task in Haskell (assuming ranges are sorted and non-overlaping):

merge ((a1,b1):(a2,b2):tail) | b1 == a2 = merge ((a1,b2):tail)
| otherwise = (a1,b1):(merge ((a2,b2):tail))
merge (h:t) = h:(merge t)
merge [] = []

@WAHa_06x36 Done with Elixir and chunk_while. The second one also looks like it could be done with either chunk_while or reduce.

(Ignore the '\t', it's a byproduct of how Elixir does strings, it's really [9]. And the result is just syntactic sugar for a list of tuples.)
image.png
image.png

@WAHa_06x36
This is straight-forward enough in Haskell:

groupSnd :: Eq t => [(a, t)] -> [([a], t)]
groupSnd = map f . groupBy (\x y -> snd x == snd y)
where f group = (map fst group, snd $ head group)

@cthulahoops That fails the requirement I forgot and put in a later reply, I think?

@WAHa_06x36 I'm not seeing that. Unless you mean that ordering? In which case it's fine.

@WAHa_06x36
*Main> groupSnd [(1, 'a'), (2, 'b'), (3, 'a')]
[([1],'a'),([2],'b'),([3],'a')]

Not quite unchanged, but the type of the function would be weird if it was.

@migratory Wow, now that is the kind of actual useful constructs I like to see! 💯 for Rust in this one.

Might consider implementing that one for myself in Swift.

@charlag @migratory Probably! But it is one that expresses the intent of the code really well.

Sign in to participate in the conversation
Mastodon

Server run by the main developers of the project 🐘 It is not focused on any particular niche interest - everyone is welcome as long as you follow our code of conduct!