CODEWITHSUNDEEP
arrayssortinghaskell
Zach Kauffman
Zach Kauffman

Reputation: 496

2d Array Sort in Haskell

I'm trying to teach myself Haskell (coming from OOP languages). Having a hard time grasping the immutable variables stuff. I'm trying to sort a 2d array in row major.

In java, for example (pseudo):

int array[3][3] = **initialize array here

for(i = 0; i<3; i++)
   for(j = 0; j<3; j++)
      if(array[i][j] < current_low)
         current_low = array[i][j]

How can I implement this same sort of thing in Haskell? If I create a temp array to add the low values to after each iteration, I won't be able to add to it because it is immutable, correct? Also, Haskell doesn't have loops, right?

Here's some useful stuff I know in Haskell:

main = do
let a = [[10,4],[6,10],[5,2]] --assign random numbers
print (a !! 0 !! 1) --will print a[0][1] in java notation
--How can we loop through the values?

Upvotes: 0

Views: 1192

Answers (2)

masonk
masonk

Reputation: 9778

Alright, well, I'll take a stab. Zach, this answer is intended to get you thinking in recursions and folds. Recursions, folds, and maps are the fundamental ways that loops are replaced in functional style. Just try to believe that in reality, the question of nested looping rarely arises naturally in functional programming. When you actually need to do it, you'll often enter a special section of code, called a monad, in which you can do destructive writes in an imperative style. Here's an example. But, since you asked for help with breaking out of loop thinking, I'm going to focus on that part of the answer instead. @leftaroundabout's answer is also very good and you fill in his definition of minimum here.

flatten :: [[a]] -> [a]
flatten [] = []
flatten xs = foldr (++) [] xs

squarize :: Int -> [a] -> [[a]]
squarize _ [] = []
squarize len xs = (take len xs) : (squarize len $ drop len xs)

crappySort :: Ord a => [a] -> [a]
crappySort [] = []
crappySort xs =
    let smallest = minimum xs
        rest = filter (smallest /=) xs
        count = (length xs) - (length rest)
    in
        replicate count smallest ++ crappySort rest

sortByThrees xs = squarize 3 $ crappySort $ flatten xs

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120711

First, your Java code does not sort anything. It just finds the smallest element. And, well, there's a kind of obvious Haskell solution... guess what, the function is called minimum! Let's see what it does:

GHCi> :t minimum
minimum :: Ord a => [a] -> a

ok, so it takes a list of values that can be compared (hence Ord) and outputs a single value, namely the smallest. How do we apply this to a "2D list" (nested list)? Well, basically we need the minimum amongst all minima of the sub-lists. So we first replace the list of list with the list of minima

allMinima = map minimum a

...and then use minimum allMinima.

Written compactly:

main :: IO ()
main = do
   let a = [[10,4],[6,10],[5,2]]   -- don't forget the indentation
   print (minimum $ map minimum a)

That's all!

Indeed "looping through values" is a very un-functional concept. We generally don't want to talk about single steps that need to be taken, rather think about properties of the result we want, and let the compiler figure out how to do it. So if we weren't allowed to use the pre-defined minimum, here's how to think about it:

  • If we have a list and look at a single value... under what circumstances is it the correct result? Well, if it's smaller than all other values. And what is the smallest of the other values? Exactly, the minimum amongst them.

    minimum' :: Ord a => [a] -> a
minimum' (x:xs)
   | x < minimum' xs  = x

  • If it's not smaller, then we just use the minimum of the other values

    minimum' (x:xs)
   | x < minxs  = x
   | otherwise  = minxs
 where minxs = minimum' xs

  • One more thing: if we recurse through the list this way, there will at some point be no first element left to compare with something. To prevent that, we first need the special case of a single-element list:

    minimum' :: Ord a => [a] -> a
minimum' [x] = x      -- obviously smallest, since there's no other element.
minimum' (x:xs)
   | x < minxs  = x
   | otherwise  = minxs
 where minxs = minimum' xs

Upvotes: 2

Related Questions