Haskell: stock span algorithm

Question

I'm trying to implement the "stock span problem" in Haskell. This is the solution I've come up with. Would like to see if there is any other idiomatic way to do this. this is O(n^2) algorithm (?) and using a stack, we can make it a O(n). Any pointers to the other higher order functions that can be used is appreciated.

import Data.List (inits)

type Quote = Int
type Quotes = [Quote]
type Span = [Int]

stockSpanQuad :: Quotes -> Span
    stockSpanQuad [] = []
    stockSpanQuad xs = map spanQ (map splitfunc  (tail $ inits xs))
      where
          spanQ (qs, q) = 1 + (length $ takeWhile (\a -> a <= q) (reverse qs))
          splitfunc xs = (init xs, last xs)

Answer 1

The link that you've provided contains a solution which uses stack data structure. The examples in every language mutate the stack, use the arrays with indexes and access the elements of the array by index. All these operations are not very common in Haskell.

Let's consider the following solution:

type Quote = Int
type Quotes = [Quote]
type Span = [Int]

stockSpanWithStack :: Quotes -> Span
stockSpanWithStack quotes = calculateSpan quotesWithIndexes []
  where
    quotesWithIndexes = zip quotes [0..]
    calculateSpan [] _ = []
    calculateSpan ((x, index):xs) stack =
      let
        newStack = dropWhile (\(y, _) -> y <= x) stack
        stockValue [] = index + 1
        stockValue ((_, x):_) = index - x
      in
        (stockValue newStack) : (calculateSpan xs ((x, index):newStack))

And let's compare it with the Python solution:

# Calculate span values for rest of the elements
for i in range(1, n):

    # Pop elements from stack whlie stack is not
    # empty and top of stack is smaller than price[i]
    while( len(st) > 0 and price[st[0]] <= price[i]):
        st.pop()

    # If stack becomes empty, then price[i] is greater
    # than all elements on left of it, i.e. price[0],
    # price[1], ..price[i-1]. Else the price[i]  is
    # greater than elements after top of stack
    S[i] = i+1 if len(st) <= 0 else (i - st[0])

    # Push this element to stack
    st.append(i)

For the stack solution, we need elements with indexes. It can be imitated like this:

quotesWithIndexes = zip quotes [0..]

The list of quotes is iterated recursively and instead of modifying a stack in every loop iteration, we can call the function with a modified value:

calculateSpan ((x, index):xs) stack =

The following line in Python (popping of elements of the stack, which are smaller than the current value):

while( len(st) > 0 and price[st[0]] <= price[i]):
    st.pop()

Can be rewritten in Haskell as:

newStack = dropWhile (\(y, _) -> y <= x) stack

And calculation of a stock value:

S[i] = i+1 if len(st) <= 0 else (i - st[0])

Can be interpreted as:

stockValue [] = index + 1
stockValue ((_, x):_) = index - x

Below it was said, that it's not a common thing to modify the state of the variables, like S[i] = ... or st.append(i). But we can recursively call the function with new stack value and prepend the current result to it:

(stockValue newStack) : (calculateSpan xs ((x, index):newStack))

Technically, we push at the beginning of the list and drop the first elements of the list, because it's idiomatic and more performant way of working with lists in Haskell.