Haskell实现CycleSort遇阻求助：作业相关技术难题

Hey there! I totally get how tricky it is to translate an imperative algorithm like CycleSort into Haskell—since Haskell’s pure, immutable approach is a big shift from Java’s in-place array modifications. Let’s walk through building a functional version together, step by step.

First, let’s recap the core logic of your Java CycleSort code to make sure we align:

// Java CycleSort snippet
public static void cycleSort(int arr[], int n) {
int writes = 0;
for (int cycleStart = 0; cycleStart < n - 1; cycleStart++) {
int item = arr[cycleStart];
int pos = cycleStart;
// Count elements smaller than item to find correct position
for (int i = cycleStart + 1; i < n; i++)
if (arr[i] < item) pos++;
// Skip if item is already in place
if (pos == cycleStart) continue;
// Skip duplicates
while (item == arr[pos]) pos++;
// Swap item into correct position
int temp = arr[pos];
arr[pos] = item;
writes++;
item = temp;
// Continue processing the cycle until we loop back to start
while (pos != cycleStart) {
// Repeat position finding and swapping
pos = cycleStart;
for (int i = cycleStart + 1; i < n; i++)
if (arr[i] < item) pos++;
while (item == arr[pos]) pos++;
temp = arr[pos];
arr[pos] = item;
writes++;
item = temp;
}
}
}

Key Differences for Haskell #

Haskell doesn’t allow in-place array modifications, so we’ll need to work with immutable data structures. We’ll start with lists (easy to read, great for learning) then move to Data.Vector for better performance.

1. List-Based CycleSort #

First, let’s write helper functions to find an element’s correct position and process individual cycles:

-- Find the correct position for an element, starting from a given index (skips duplicates)
findCorrectPos :: Ord a => a -> [a] -> Int -> Int
findCorrectPos x xs start =
    let smallerCount = length $ filter (< x) (drop start xs)
        initialPos = start + smallerCount
        skipDuplicates pos
            | pos >= length xs = pos
            | xs !! pos == x = skipDuplicates (pos + 1)
            | otherwise = pos
    in skipDuplicates initialPos

-- Process a single cycle, returning the updated list and number of writes
processCycle :: Ord a => [a] -> Int -> (Int, [a])
processCycle xs cycleStart =
    let item = xs !! cycleStart
        pos = findCorrectPos item xs cycleStart
    in if pos == cycleStart
        then (0, xs)  -- Element is already in place, no changes needed
        else processCycle' xs item pos cycleStart 1
    where
        processCycle' currentList currentItem currentPos start writes
            | currentPos == start = (writes, currentList)  -- Cycle complete
            | otherwise =
                let nextItem = currentList !! currentPos
                    -- Replace the element at currentPos with currentItem
                    updatedList = take currentPos currentList ++ [currentItem] ++ drop (currentPos + 1) currentList
                    nextPos = findCorrectPos nextItem updatedList start
                    nextPos' = skipDuplicates nextItem updatedList nextPos
                in processCycle' updatedList nextItem nextPos' start (writes + 1)
        skipDuplicates x lst p
            | p >= length lst = p
            | lst !! p == x = skipDuplicates x lst (p + 1)
            | otherwise = p

-- Main CycleSort function: process all cycles and return (write count, sorted list)
cycleSort :: Ord a => [a] -> (Int, [a])
cycleSort xs = foldl processCycleHelper (0, xs) [0 .. length xs - 2]
    where
        processCycleHelper (totalWrites, currentList) start =
            let (cycleWrites, newList) = processCycle currentList start
            in (totalWrites + cycleWrites, newList)

Test the List Version

main :: IO ()
main = do
    let testArr = [3, 1, 2, 5, 4, 3]
        (writes, sortedArr) = cycleSort testArr
    putStrLn $ "Original array: " ++ show testArr
    putStrLn $ "Sorted array: " ++ show sortedArr
    putStrLn $ "Number of writes: " ++ show writes

2. Efficient Vector-Based Version #

Lists have O(n) access time with !!, so for larger datasets, use Data.Vector (O(1) access):

import qualified Data.Vector as V
import Data.Vector (Vector)

findCorrectPosVec :: Ord a => a -> Vector a -> Int -> Int
findCorrectPosVec x vec start =
    let smallerCount = V.length $ V.filter (< x) (V.drop start vec)
        initialPos = start + smallerCount
        skipDuplicates pos
            | pos >= V.length vec = pos
            | vec V.! pos == x = skipDuplicates (pos + 1)
            | otherwise = pos
    in skipDuplicates initialPos

processCycleVec :: Ord a => Vector a -> Int -> (Int, Vector a)
processCycleVec vec cycleStart =
    let item = vec V.! cycleStart
        pos = findCorrectPosVec item vec cycleStart
    in if pos == cycleStart
        then (0, vec)
        else processCycle' vec item pos cycleStart 1
    where
        processCycle' currentVec currentItem currentPos start writes
            | currentPos == start = (writes, currentVec)
            | otherwise =
                let nextItem = currentVec V.! currentPos
                    -- Update the vector at currentPos with currentItem
                    updatedVec = V.update currentVec $ V.singleton (currentPos, currentItem)
                    nextPos = findCorrectPosVec nextItem updatedVec start
                    nextPos' = skipDuplicates nextItem updatedVec nextPos
                in processCycle' updatedVec nextItem nextPos' start (writes + 1)
        skipDuplicates x v p
            | p >= V.length v = p
            | v V.! p == x = skipDuplicates x v (p + 1)
            | otherwise = p

cycleSortVec :: Ord a => Vector a -> (Int, Vector a)
cycleSortVec vec = foldl helper (0, vec) [0 .. V.length vec - 2]
    where
        helper (totalWrites, currentVec) start =
            let (cycleWrites, newVec) = processCycleVec currentVec start
            in (totalWrites + cycleWrites, newVec)

-- Test the Vector Version
mainVec :: IO ()
mainVec = do
    let testVec = V.fromList [3, 1, 2, 5, 4, 3]
        (writes, sortedVec) = cycleSortVec testVec
    putStrLn $ "Original vector: " ++ show testVec
    putStrLn $ "Sorted vector: " ++ show sortedVec
    putStrLn $ "Number of writes: " ++ show writes

Notes #

• The list version is great for understanding the algorithm, but the vector version is much more efficient for real-world use.
• We preserved the write-counting functionality from your Java code, so you can compare behavior directly.
• The core cycle-processing logic mirrors your Java code—we just adapted it to immutable data structures instead of in-place swaps.

内容的提问来源于stack exchange，提问作者S.Pas