Saving function results

Learn
1

I’m learning haskell. For practice, I wrote a simple sorting algorithm. This raised a question.

Here is the code:

selectionSort :: [Int] -> [Int]
selectionSort [] = []
selectionSort xs = smallestValue xs : selectionSort (removeValue xs (smallestValue xs))

    where

        smallestValue :: [Int] -> Int
        smallestValue xs = smallestSearch xs 100
            where
                smallestSearch :: [Int] -> Int -> Int
                smallestSearch [] s = s
                smallestSearch (x:xs) s = if x < s then smallestSearch xs x else smallestSearch xs s
        
        removeValue :: [Int] -> Int -> [Int]
        removeValue (x:xs) v = if x == v then xs else x : removeValue xs v

In the selectionSort function, I am calling smallestValue two times (inefficient).

My understanding is that there aren’t really variables in Haskell. (Even variable = smallestValue would just be a function that calls smallestValue every time.)

Hence my question: How can I save the smallest element?

Thanks for your help!

1 Like
2

Why not

let smol = smallestValue xs
in smol : selectionSort (removeValue xs smol)

?

3 Likes
3

In cases where you do what OP did, is the compiler smart enough to make those refer to create a single value for the two redundant calls?

4

As you become more experienced with Haskell, you’ll write something that tries to only manipulate lists by pattern matching and prepending elements to an accumulator. The below finds the largest element while keeping track of already examined elements that are at most as big, and yet to be examine elements that might be bigger, the accumulator contains previously removed maxima in ascending order.

selectionSort :: [Int] -> [Int]
selectionSort [] = []
selectionSort (a : as) = go [] [] as a
  where
    go :: [Int] -> [Int] -> [Int] -> Int -> [Int]
    go acc smalls (l : ls) big
        | l > big   = go acc (big : smalls) ls l
        | otherwise = go acc (l : smalls) ls big
    go acc (small : smalls) [] big = go (big : acc) [] smalls small
    go acc [] [] big = big : acc
1 Like
5

I ran ghc -ddump-simpl and the answer seems “No, the compiler is not that smart.”
In general I recall values are memoised, not functions.
`

1 Like
6

Under appropriate conditions (monomorphic expression, strict evaluation, optimisation, …) CSE (common sub-expression elimination) may take place, but here it does not.

1 Like