DEV Community

druchan
druchan

Posted on • Edited on

Calculating the maximum profit from stocks: Purescript Leetcode Solution (Updated to use Typeclass)

#purescript #typeclass #functional #leetcode

In the last note posted, we "implicitly" defined some valid trades.

Two data structures specifically had this notion associated with them:

-- type Day = Int -- type Price = Int type StockDay = Tuple Price Day -- and data BuySell = BuySell StockDay StockDay
Enter fullscreen mode Exit fullscreen mode

Two StockDays could be valid only if they happen on subsequent days.

That is:

a = Tuple _ 1 b = Tuple _ 6 c = Tuple _ 8 d = Tuple _ 4
Enter fullscreen mode Exit fullscreen mode

In this, a followed by b can be a valid trade because the "day" order makes sense. (That is a is on 1st day and b is on 6th day - buy on 1st and sell on 6th).

But c followed by d (and b followed by d) are not valid because the day orders are reversed.

This notion comes into the picture when we "pair" these to make a BuySell combination.

We expressed this as a Maybe:

makeBuySell :: StockDay -> StockDay -> Maybe BuySell makeBuySell t1@(Tuple p1 a) t2@(Tuple p2 b) = if a < b && p1 < p2 then Just (BuySell t1 t2) else Nothing
Enter fullscreen mode Exit fullscreen mode

That a < b part takes care of the "valid trade" logic.

It's OK and there's no need to "improve" this...

But now, there's also this other function that we use in our computation:

isValidTradeDayOrder :: BuySell -> BuySell -> Boolean isValidTradeDayOrder (BuySell (Tuple _ a) (Tuple _ b)) (BuySell (Tuple _ c) (Tuple _ d)) = (a < b && c < d && c > b) || (c < d && a < b && d < a)
Enter fullscreen mode Exit fullscreen mode

Here, we're trying to confirm if two buy-sell pairs are actually valid by making sure the dates/days align. (Remember that within a BuySell pair, the StockDays are valid thanks to our makeBuySell function. Essentially, a BuySell represents valid, profitable buy-and-sell operation).

Again, though, in the case of a isValidTradeDayOrder, we're dealing with this idea of "valid trade".

I decided (or rather, wanted to experiment) if this general idea of a "valid trade" can be encoded into the code as a general function.

Purescript, like Haskell, allows you to define your own typeclasses and then define instances for your data types.

So, here's a generic ValidTrade class:

class ValidTrade a where validTrade :: a -> a -> Boolean
Enter fullscreen mode Exit fullscreen mode

Any datatype using the ValidTrade class must simply describe a validTrade function.

And so, here are the definitions for both the StockDay and BuySell data types:

instance ValidTrade BuySell where validTrade (BuySell (Tuple _ a) (Tuple _ b)) (BuySell (Tuple _ c) (Tuple _ d)) = (a < b && c < d && c > b) || (c < d && a < b && d < a) instance ValidTrade StockDay where validTrade (Tuple _ d1) (Tuple _ d2) = d1 < d2
Enter fullscreen mode Exit fullscreen mode

I also added an infix to help make the code a little succinct:

infix 1 validTrade as ??
Enter fullscreen mode Exit fullscreen mode

Now, I could get rid of the isValidTradeDayOrder function in totality and replace some instances with ??:

makeBuySell :: StockDay -> StockDay -> Maybe BuySell makeBuySell t1@(Tuple p1 _) t2@(Tuple p2 _) = if (t1 ?? t2) && p1 < p2 then Just (BuySell t1 t2) else Nothing bestBuySellPair :: BuySell -> SortedArray (BuySell) -> Int -> Maybe BestCandidate -> Maybe BestCandidate bestBuySellPair buySell (SortedArray []) maxProfitSoFar bestTradeSoFar = if buySellProfit buySell > maxProfitSoFar then (Just $ Tuple buySell Nothing) else bestTradeSoFar bestBuySellPair buySell (SortedArray tradePairs) maxProfitSoFar bestTradeSoFar = case head tradePairs of Just h -> -- notice the ?? here. we've replaced the `isValidTradeDayOrder` function with ?? if ((buySell ?? h) && (buySellProfit buySell + buySellProfit h) > maxProfitSoFar) then bestBuySellPair buySell (fromMaybe (SortedArray []) (map SortedArray $ tail tradePairs)) (buySellProfit buySell + buySellProfit h) (Just $ Tuple buySell (Just h)) else bestBuySellPair buySell (fromMaybe (SortedArray []) (map SortedArray $ tail tradePairs)) maxProfitSoFar bestTradeSoFar Nothing -> if buySellProfit buySell > maxProfitSoFar then (Just $ Tuple buySell Nothing) else bestTradeSoFar
Enter fullscreen mode Exit fullscreen mode

And the script continues to run just fine:

> totalProfits [3,1,0,0,5,4,1] 5 > totalProfits [3,1,0,0,1] 1 > totalProfits [3,1,0,0,1,2,3] 3
Enter fullscreen mode Exit fullscreen mode

Updated source-code here.

Top comments (0)