4 ms·

Typical Haskell coding post with no mention of order or efficiency of the algorithm solutions. The thing is, even in basic coding quizes, if the interviewer is

Typical Haskell coding post with no mention of order or efficiency of the algorithm solutions. The thing is, even in basic coding quizes, if the interviewer is worth their salt, they will ask about how to improve the efficiency of the naive solutions first put forward, like the palindrome answer in this post. What is the order of sumNToTotal?

Paracompact 1y ago
The execution order, or the order of the output list? The latter should be self-evident from the function body (first elements get collected first), and the former holds no tricks either since filters are evaluated from the head first, and concat (<>) allows lazy access to the first list's elements. This is just a beginner's Haskell post. If an interviewer really meant to test optimization knowledge, I would hope they wouldn't ask me to optimize one O(n) utility function into another.
dmurray 1y ago
It does discuss performance and points out some places where the Haskell implementation makes the natural naive solutions performant. > While it's true that sort has an O(nlogn) performance profile, one interesting thing here is that sorting is lazy in Haskell! This means that if our two strings are unequal, they will only be sorted far enough to determine inequality! I don't understand exactly how this works - don't all O(n log n) sorting algorithms still have to do some work on the other elements of the list before pulling out the smallest one? If you just scanned and pulled the smallest one to the front each time that is O(n^2). And there's an implementation detail here that differences at the start of the sorted string will be caught more quickly than at the end, so real-world behaviour is dependent on your choice of sort order. Agreed that the performance analysis is quite superficial and that some of the solutions like sum NToTotal must be very sub-optimal.
deleted 1y ago
[deleted]
iamevn 1y ago
with N as the length of the subsets and X as the length of input, `combinations n xs` basically walks through list xs and at each element, conses that element onto each combination of size n-1 of later elements in the list then appends those resulting lists together. this is on the order of N * nCr(X, N) aka O(NX!/(N!(X-N)!)) which dominates the overall runtime. the final filter walks through each combination and does O(N) work at each element to find the ones that sum to the desired amount, again O(NX!/(N!(X-N)!))
kqr 1y ago
The matchesSum check is constant in the length of the input list. The filter adds an iteration over all results of (combinations n xs). If the complexity of (combinations n) is T(n) in xs, then by analogy of its recursive definition we have two recursive calls that are T(n-1), we have an fmap that is O(1) and a concatenation that is O(1). That sets up the recurrence T(n) = 2T(n-1) making the (combinations n) function O(n) in xs. Thus the whole thing is O(n²). It's not like this is particularly hard for Haskell. If anything, it's often easier because we can set up the recurrence by analogy with the definition.
- iamevn 1y ago
  can you not narrow it down further to O(k * nCr(n, k)) (n=size of input, k=combination size) since it does k conses for each of the nCr(n, k) combinations? (the final filter sums k elements nCr(n, k) times as well)
- benmmurphy 1y ago
  how is combinations O(n)? for n choose 3 generating combinations is going to approach n^3 since the formula is basically (n * n * n) / constant and for sumToAny generating all the combinations is 2^n.
Tainnor 1y ago
As much as I find Haskell elegant for many things, I have to agree. It reminds me of the infamous Haskell "quicksort" which isn't actually quicksort because it's not in place. I think not every piece of code needs to be hyper-optimised and in those cases, higher-level (declarative) languages where you don't specify every detail of the algorithm can give rise to very elegant code. But writing very performant Haskell code is a bit trickier. In the anagram case, there's a straightforward O(n) solution where you count the occurrence of each letter in a hash map for both words and compare those. That can be written in Haskell too, of course, but it's not going to be as short.
- jose_zap 1y ago
  Interestingly, the naive solution presented in this article is O(n) thanks to laziness.
  - deleted 1y ago
    [deleted]
  - foldr 1y ago
    It’s O(n log n). If the strings contain the same letters then you end up fully sorting both lists, and there’s no magical way of doing that in O(n) time with a general purpose sorting algorithm. The article is just saying that the best case performance improves because you don’t have to fully sort both lists in the case where the two words are not anagrams. There are other cases where laziness works its magic in relation to sorting, though. For example, “sort the list and then take the first element” is (with a suitable implementation of ‘sort’) an O(n) implementation of “find min/max element of list” in Haskell.

Paracompact 1y ago

The execution order, or the order of the output list? The latter should be self-evident from the function body (first elements get collected first), and the former holds no tricks either since filters are evaluated from the head first, and concat (<>) allows lazy access to the first list's elements. This is just a beginner's Haskell post. If an interviewer really meant to test optimization knowledge, I would hope they wouldn't ask me to optimize one O(n) utility function into another.

dmurray 1y ago

It does discuss performance and points out some places where the Haskell implementation makes the natural naive solutions performant. > While it's true that sort has an O(nlogn) performance profile, one interesting thing here is that sorting is lazy in Haskell! This means that if our two strings are unequal, they will only be sorted far enough to determine inequality! I don't understand exactly how this works - don't all O(n log n) sorting algorithms still have to do some work on the other elements of the list before pulling out the smallest one? If you just scanned and pulled the smallest one to the front each time that is O(n^2). And there's an implementation detail here that differences at the start of the sorted string will be caught more quickly than at the end, so real-world behaviour is dependent on your choice of sort order. Agreed that the performance analysis is quite superficial and that some of the solutions like sum NToTotal must be very sub-optimal.

deleted 1y ago

[deleted]

iamevn 1y ago

with N as the length of the subsets and X as the length of input, `combinations n xs` basically walks through list xs and at each element, conses that element onto each combination of size n-1 of later elements in the list then appends those resulting lists together. this is on the order of N * nCr(X, N) aka O(NX!/(N!(X-N)!)) which dominates the overall runtime. the final filter walks through each combination and does O(N) work at each element to find the ones that sum to the desired amount, again O(NX!/(N!(X-N)!))

kqr 1y ago

The matchesSum check is constant in the length of the input list. The filter adds an iteration over all results of (combinations n xs). If the complexity of (combinations n) is T(n) in xs, then by analogy of its recursive definition we have two recursive calls that are T(n-1), we have an fmap that is O(1) and a concatenation that is O(1). That sets up the recurrence T(n) = 2T(n-1) making the (combinations n) function O(n) in xs. Thus the whole thing is O(n²). It's not like this is particularly hard for Haskell. If anything, it's often easier because we can set up the recurrence by analogy with the definition.

iamevn 1y ago
can you not narrow it down further to O(k * nCr(n, k)) (n=size of input, k=combination size) since it does k conses for each of the nCr(n, k) combinations? (the final filter sums k elements nCr(n, k) times as well)
benmmurphy 1y ago
how is combinations O(n)? for n choose 3 generating combinations is going to approach n^3 since the formula is basically (n * n * n) / constant and for sumToAny generating all the combinations is 2^n.

Tainnor 1y ago

As much as I find Haskell elegant for many things, I have to agree. It reminds me of the infamous Haskell "quicksort" which isn't actually quicksort because it's not in place. I think not every piece of code needs to be hyper-optimised and in those cases, higher-level (declarative) languages where you don't specify every detail of the algorithm can give rise to very elegant code. But writing very performant Haskell code is a bit trickier. In the anagram case, there's a straightforward O(n) solution where you count the occurrence of each letter in a hash map for both words and compare those. That can be written in Haskell too, of course, but it's not going to be as short.

jose_zap 1y ago
Interestingly, the naive solution presented in this article is O(n) thanks to laziness.
- deleted 1y ago
  [deleted]
- foldr 1y ago
  It’s O(n log n). If the strings contain the same letters then you end up fully sorting both lists, and there’s no magical way of doing that in O(n) time with a general purpose sorting algorithm. The article is just saying that the best case performance improves because you don’t have to fully sort both lists in the case where the two words are not anagrams. There are other cases where laziness works its magic in relation to sorting, though. For example, “sort the list and then take the first element” is (with a suitable implementation of ‘sort’) an O(n) implementation of “find min/max element of list” in Haskell.