Haskell技术问询：ForM循环值未保存及最长递增子序列开发

Hey Greg, let’s work through your two Haskell issues step by step—they’re both great examples of how functional programming patterns differ from imperative ones, so let’s break them down.

First up: the classic "why isn’t my variable updating in forM?" issue. The root cause here is that Haskell is a pure functional language—there’s no mutable state by default. When you try to "update" a variable inside a forM loop, you’re actually creating a new binding each time, not modifying the original value.

For example, if you wrote something like this:

badForMExample :: IO Int
badForMExample = do
  let count = 0
  forM [1..5] $ \_ -> do
    let count = count + 1  -- This creates a NEW `count`, not modifying the original
    print count
  return count  -- This returns the original 0, not 5!

Fixes for This: #

You have two solid options here, depending on your use case:

1. Use the State Monad for Managed State
   If you need to keep track of state through the loop, the State monad lets you safely accumulate values without mutation:

   import Control.Monad.State
   
   sumWithState :: [Int] -> Int
   sumWithState nums = execState (forM nums $ \x -> do
       current <- get  -- Get the current state value
       put (current + x)  -- Update the state
     ) 0  -- Initial state value
   

2. Replace forM with a Fold (Pure Functional Approach)
   For many cases, a fold is more idiomatic and efficient than a monadic loop. Folds are designed to accumulate values through a list:

   import Data.List (foldl')
   
   sumWithFold :: [Int] -> Int
   sumWithFold = foldl' (+) 0
   

   foldl' is strict, so it avoids unnecessary thunks and performs better for large lists.

Next, let’s tackle the LIS problem. Your input format is:

• First number = number of test cases
• For each test case: a number (length of the list) followed by the list itself
• Example input: 1 5 1 2 9 6 8 (1 test case, list length 5, list [1,2,9,6,8])

First, let’s implement an efficient LIS length calculator (O(n log n) time complexity, which is better than the naive O(n²) approach):

import Data.List (foldl')

-- Calculate the length of the longest increasing subsequence
lisLength :: Ord a => [a] -> Int
lisLength = length . foldl' update []
  where
    -- Update our list of smallest possible tail values for subsequences of each length
    update [] x = [x]
    update xs x
      | x > last xs = xs ++ [x]  -- Extend the longest subsequence
      | otherwise = replaceSmallestTail xs x  -- Replace the first tail >= x

    -- Use binary search to find the index of the first element >= x
    replaceSmallestTail xs x = take idx xs ++ [x] ++ drop (idx + 1) xs
      where
        idx = binarySearch xs x
        binarySearch [] _ = 0
        binarySearch ys y
          | y <= head ys = 0
          | y > last ys = length ys
          | otherwise = let mid = length ys `div` 2
                            (left, right) = splitAt mid ys
                        in if y <= head right
                           then binarySearch left y
                           else mid + binarySearch right y

Then, let’s handle the input parsing and process each test case:

import System.IO (getContents)

-- Parse input into test cases and compute LIS lengths for each
processInput :: String -> [Int]
processInput input = let allNums = map read $ words input
                         numTestCases = head allNums
                         rest = tail allNums
                     in map lisLength $ parseTestCases rest
  where
    parseTestCases [] = []
    parseTestCases (n:xs) = take n xs : parseTestCases (drop n xs)

-- Main function to read input and print results
main :: IO ()
main = do
    input <- getContents
    let results = processInput input
    mapM_ print results

If You Need the Actual Subsequence (Not Just Length): #

If you want to return the actual LIS instead of just its length, you can modify the algorithm to track predecessors (this adds a bit of complexity but is doable):

import Data.List (foldl', elemIndex)
import Data.Maybe (fromJust)

lis :: Ord a => [a] -> [a]
lis xs = reverse $ buildSequence xs tails preds (length tails - 1)
  where
    -- (tails list, predecessors list)
    (tails, preds) = foldl' update ([], []) xs
    update (ts, ps) x
      | null ts = ([x], [-1])
      | x > last ts = (ts ++ [x], ps ++ [length ts - 1])
      | otherwise = let idx = binarySearch ts x
                        newTs = take idx ts ++ [x] ++ drop (idx+1) ts
                        newPs = if idx == 0 then ps else take idx ps ++ [idx-1] ++ drop (idx+1) ps
                    in (newTs, newPs)
    binarySearch ys y
      | y <= head ys = 0
      | y > last ys = length ys
      | otherwise = let mid = length ys `div` 2
                        (left, right) = splitAt mid ys
                    in if y <= head right
                       then binarySearch left y
                       else mid + binarySearch right y
    buildSequence xs ts ps idx
      | idx == -1 = []
      | otherwise = xs !! idx : buildSequence xs ts ps (ps !! idx)

This version tracks the indices of predecessors so we can reconstruct the actual subsequence.

内容的提问来源于stack exchange，提问作者Greg