如何将计算指定范围倍数数量的C程序转换为Haskell程序？

Hey there! Let's work through converting your C multiple-counting program to Haskell. First, let's make sure we're on the same page with the requirement: given integers a and b, count how many numbers between 1 and b (inclusive) are divisible by any integer from 2 to a (inclusive). As you noted, when a=3 and b=30, the answer is 20—makes sense, since we're counting multiples of 2 or 3 in that range.

First: A Simple (But Naive) Implementation #

If you're just getting started with Haskell, a straightforward approach uses sets to avoid counting duplicates (since numbers like 6 get divisible by both 2 and 3). Here's how that looks:

import Data.Set (Set)
import qualified Data.Set as Set

countMultiples :: Int -> Int -> Int
countMultiples a b = Set.size $ foldr addMultiples Set.empty [2..a]
  where
    addMultiples n existing = Set.union existing (Set.fromList [n, 2*n..b])

How this works:

• We start with an empty set.
• For each number n from 2 to a, we generate all its multiples up to b and add them to the set (sets automatically handle duplicates).
• Finally, we just take the size of the resulting set to get our count.

This is easy to read and matches the "collect all valid numbers" logic you might have used in C, but it's not great for large values of a or b—generating and merging sets can get slow and memory-heavy.

Better: Use the Inclusion-Exclusion Principle #

For efficiency, we can use the inclusion-exclusion principle to calculate the count without generating every valid number. This avoids duplicates mathematically instead of relying on data structures.

Here's an implementation:

import Data.List (subsequences)

-- Calculate greatest common divisor (reusing Prelude's gcd is fine too)
gcd' :: Int -> Int -> Int
gcd' x 0 = x
gcd' x y = gcd' y (x `mod` y)

-- Calculate least common multiple of two numbers
lcm' :: Int -> Int -> Int
lcm' x y = x * y `div` gcd' x y

-- Calculate LCM of a list of numbers
lcmList :: [Int] -> Int
lcmList = foldl lcm' 1

countMultiples' :: Int -> Int -> Int
countMultiples' a b = sum $ map computeTerm nonEmptySubsets
  where
    -- Generate all non-empty subsets of [2..a]
    nonEmptySubsets = filter (not . null) $ subsequences [2..a]
    
    -- Compute the contribution of each subset to the final count
    computeTerm subset = 
      let subsetSize = length subset
          subsetLcm = lcmList subset
      in if subsetLcm > b
         then 0  -- No multiples of this LCM exist in 1..b
         else if odd subsetSize
              then b `div` subsetLcm  -- Add counts for odd-sized subsets
              else -(b `div` subsetLcm)  -- Subtract counts for even-sized subsets

How this works:

1. Subsets: We generate every non-empty group of numbers from 2 to a. For a=3, that's [2], [3], [2,3].
2. LCM Calculation: For each subset, we find the least common multiple (LCM) of its elements—this tells us the smallest number divisible by all elements in the subset.
3. Inclusion-Exclusion:
   • Add the count of multiples of single numbers (odd subset size: +15 for 2, +10 for 3).
   • Subtract the count of multiples of their LCM (even subset size: -5 for 6, since those numbers were counted twice).
   • For larger subsets, we alternate adding/subtracting based on subset size parity.

Testing this with countMultiples' 3 30 gives exactly 20, which matches your example.

Optimizing for Larger Values #

If you're working with big a (like a=20 or more), generating all subsets can get slow. We can add a pruning step to skip subsets where the LCM already exceeds b (since those contribute nothing to the count):

countMultiplesOptimized :: Int -> Int -> Int
countMultiplesOptimized a b = go 0 1 1 [2..a]
  where
    go total currentLcm sign (x:xs)
      | newLcm > b = go total currentLcm sign xs  -- Skip this branch, LCM is too big
      | otherwise = let term = sign * (b `div` newLcm)
                    in go (total + term) newLcm (-sign) xs  -- Include x in the subset
                       + go total currentLcm sign xs  -- Exclude x from the subset
    go total _ _ [] = total
    newLcm = lcm' currentLcm x

This recursive approach builds subsets incrementally and stops exploring paths where the LCM would be larger than b, saving a ton of computation time for big inputs.

Common Pitfalls When Converting from C #

If you hit snags during conversion, here are a few things to watch for:

• Imperative vs Functional: C uses loops and mutable variables, but Haskell relies on recursion, folds, and pure functions. The set-based example is a good bridge if you're used to collecting values in a loop.
• Duplicate Handling: In C, you might use a boolean array to mark valid numbers; in Haskell, sets or inclusion-exclusion are the idiomatic alternatives.
• Integer Overflow: Haskell's Int is fixed-size (like C's int), but you can use Integer for arbitrary-precision numbers if you're working with very large a or b.

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