Haskell: Appending to a list from multiple locations in a program
Question: I would like to have a list that may be updated (appended to) from more than
one location in the code. Since in haskell, [`calling a function once is the
same as calling it twice and discarding the result of the first
call`](https://www.fpcomplete.com/school/starting-with-haskell/basics-of-
haskell/3-pure-functions-laziness-io), what is the best way for me to manage
this list if side effects are not allowed? I've thought of passing the list
through each time each time I need to append to it, but I don't know if that
would be sufficient for what I want to accomplish. The [algorithm that I'm
implementing](http://video.mit.edu/watch/introduction-to-algorithms-
lecture-20-dynamic-programming-ii-text-justification-blackjack-14035/) uses
memoization [edit not dynamic programming] and stores a possible list of
optimal winnings in a helper list. Would it be a good idea to simulate a
global variable using monads and states or is there a better way to go about
this?

Edit: This is how I implemented it in python:

    
    
    def BJ(i):                                                                                                                                                                                                  
        if i in BJList:                                                                                                                                                                                         
            return BJList[i]                                                                                                                                                                                    
        else:                                                                                                                                                                                                   
            options = [0]                                   # if you walk away                                                                                                                                  
            if n-i < 4:                                     # not enough cards to play                                                                                                                          
                return 0                                                                                                                                                                                        
            for p in range(2,(n - i)):                      # number of cards taken                                                                                                                             
                player = c[i] + c[i+2] + sum(c[i+4:i+p+2])                                                                                                                                                      
                # when p is 2                                                                                                                                                                                   
                if player > 21:                                                                                                                                                                                 
                    options.append(-1 + BJ(i + p + 2))                                                                                                                                                          
                    break                                   # breaks out of for(p)                                                                                                                              
                dealer = 0                                                                                                                                                                                      
                d1 = 0                                                                                                                                                                                          
                for d in range(2,n-i-p+1): # python ranges are not inclusive                                                                                                                                    
                    d1 = d                                                                                                                                                                                      
                    dealer = c[i+1] + c[i+3] + sum(c[i+p+2:i+p+d])                                                                                                                                              
                    if dealer >= 17:                                                                                                                                                                            
                        break                               # breaks out of for(d)                                                                                                                              
                if dealer < 17 and i + p + d >= n:          # doesn't change results, maybe                                                                                                                     
                    dealer = 21                             # make it be more like haskell version                                                                                                              
                if dealer > 21:                                                                                                                                                                                 
                    dealer = 0                                                                                                                                                                                  
                dealer += .5                                # dealer always wins in a tie                                                                                                                       
                options.append(cmp(player, dealer) + BJ(i + p + d1))                                                                                                                                            
            BJList[i] = (max(options))                                                                                                                                                                          
            return max(options)                                                                                                                                                                                 
    
    c = [10,3,5,7,5,2,8,9,3,4,7,5,2,1,5,8,7,6,2,4,3,8,6,2,3,3,3,4,9,10,2,3,4,5]                                                                                                                                 
    BJList = {}                                                                                                                                                                                                 
    n = len(c)                                                                                                                                                                                                  
    print "array:" +  str(c)                                                                                                                                                                                    
    print BJ(0)  
    

My question refers to the `options` list. Is there a way to implement the
`options` list that would allow me to manipulate it in both `options.append`
locations?

Edit: This is my final implementation in Haskell (both programs concur):

    
    
    import qualified Data.MemoCombinators as Memo                                                                                                                                                               
    
    deck = [10,3,5,7,5,2,8,9,3,4,7,5,2,1,5,8,7,6,2,4,3,8,6,2,3,3,3,4,9,10,2,3,4,5]                                                                                                                              
    dsize = length deck                                                                                                                                                                                         
    
    getPlayerScore :: Int -> Int -> Int                                                                                                                                                                         
    getPlayerScore i p                                                                                                                                                                                          
      | i + 2 + p <= dsize =                                                                                                                                                                                    
        deck !! i + deck !! (i + 2) + (sum $ take (p-2) $ drop (i + 4) deck)                                                                                                                                    
      | otherwise = 0                                                                                                                                                                                           
    
    getDealerScoreAndHitCount :: Int -> Int -> (Int, Int)                                                                                                                                                       
    getDealerScoreAndHitCount i p  -- gets first two cards                                                                                                                                                      
      | i + 2 + p <=                                                                                                                                                                                            
        dsize = getDSAHC' (deck !! (i + 1) + deck !! (i + 3)) (i+2+p)                                                                                                                                           
      | otherwise = (0,0)                                                                                                                                                                                       
    
    getDSAHC' :: Int -> Int -> (Int, Int) -- gets the remaining cards dealer hits                                                                                                                               
    getDSAHC' baseScore cardIndex                                                                                                                                                                               
      | baseScore >= 17 = (baseScore,0)                                                                                                                                                                         
      | cardIndex < dsize = (fst result, snd result  + 1)                                                                                                                                                       
      | otherwise = (0,0)                                                                                                                                                                                       
        where                                                                                                                                                                                                   
          result = getDSAHC' (baseScore + deck !! cardIndex) (cardIndex + 1)                                                                                                                                    
    
    takeWhile' :: (a -> Bool) -> [a] -> [a]                                                                                                                                                                     
    takeWhile' p (x:xs) =                                                                                                                                                                                       
      if p x                                                                                                                                                                                                    
        then x:takeWhile' p xs                                                                                                                                                                                  
                    else [x]                                                                                                                                                                                    
    takeWhile' p [] = []                                                                                                                                                                                        
    
    getHandOutcome :: Int -> Int -> Int                                                                                                                                                                         
    getHandOutcome pValue dValue                                                                                                                                                                                
            | pValue > 21 = -1                                                                                                                                                                                  
            | dValue == 0 = 0                                                                                                                                                                                   
            | pValue > dValue = 1                           -- player beats dealer                                                                                                                              
            | dValue > 21 = 1                               -- dealer busts                                                                                                                                     
            | otherwise = -1                                -- dealer wins ties                                                                                                                                 
    
    blackjack :: Int -> Int                                                                                                                                                                                     
    blackjack i                                                                                                                                                                                                 
      | dsize - i < 4 = 0                                                                                                                                                                                       
      | otherwise = maximum options                                                                                                                                                                             
        where                                                                                                                                                                                                   
          options =                                                                                                                                                                                             
            [0] ++ map score (takeWhile' (\(p,_,_) -> p <= 21) (map result [2 ..dsize-i-1]))                                                                                                                    
          score (pValue,dValue,mCards) =      -- mcards is total cards taken in current hand                                                                                                                    
            (getHandOutcome pValue dValue) + bjMemo (i + mCards)                                                                                                                                                
          result p = -- 'p' represents the num of cards player is going to receive                                                                                                                              
            (getPlayerScore i p, fst (getDealerScoreAndHitCount i p),                                                                                                                                           
               2 + p + snd (getDealerScoreAndHitCount i p))                                                                                                                                                     
    
    bjMemo :: Int -> Int                                                                                                                                                                                        
    bjMemo = Memo.integral blackjack 
    
    main :: IO()                                                                                                                                                                                                
    main =                                                                                                                                                                                                      
      do                                                                                                                                                                                                        
        print $ blackjack 0 
    


Answer: In general I see 3 solutions, with decreasing 'appealing' to Haskellers:

  1. Write the algorithm in a purely functional way

     * Pros: No side effects, beautiful
     * Cons: You might have to rewrite the algorithm if it is given in imperative style (which is the case here)
  2. Use the `State` monad to _emulate_ state, because it essentially just 'hides' additional arguments to your function. 

     * Pro: Imperative feeling
     * Cons: Monadic code, which is in general harder to reason about and not as easy reusable
     * Example:
        
                workerState :: State [Int] ()
        workerState = do
          modify (++ [21])
          {- lots of stuff happening -}
          modify (++ [21])
        
        -- E.g. in repl
        > runState workerState []
        

  3. Use side effects. This means use either the `ST` monad or some sort of mutable references like `IORef`. 

     * Pro: Real mutability, minimal changes to original algorithm due to monadic style
     * Cons: All from `State` \+ the ultimate evil: _side effects_
     * Example:
        
                workerST :: STRef s [Int] -> ST s ()
        workerST ref = do
          modifySTRef ref (++ [21])
          {- lots of stuff happening -}
          modifySTRef ref (++ [21])
        
        -- E.g. in repl:
        > runST $ do
            r <- newSTRef []
            workerST r
        

Note that in general _appending_ to a list in haskell is slow because the
standard list type is a single linked list, where only prepend is O(1).

Having said that, if you use variant 1 (purely functional), you also have the
benefit of using libraries like [memo-
combinators](http://hackage.haskell.org/package/data-memocombinators/), giving
you memoization almost for free: Given a function `bj` that calculates the
best score, we can memoize it like that:

    
    
    bj :: Int -> Score
    bj i = 
      undefined -- purely functional algorithm, replace recursive calls with bjMemo
    
    bjMemo :: Int -> Score
    bjMemo = Memo.integral bj
    

