Haskell Nested Loop accumulator

Question

I'm working on modifying my server side programming language from PHP to Haskell and am therefore not fully acquainted with functional language design.

Here I want to convert part of the processing code of something like the following php function to Haskell:

function loop($A) {
  $array1 = array();
  $num = (int)$A;
  if ($num == 0)
    $array1 = "0";
  for (int $i=0; $i<$num; $i++)
    foreach (loop($i-$num) as &$value)
      $array1[] = "+ ".$value." ";  //concat
  return $array1;
}

I imagine there would be heavy use of the map/mapM_ functions, but how would the accumulation work? I'm starting to think that the added safety won't be worth the transformation at this point.

Thanks.

Answer 1

Here's the php as it stands at the time I'm answering:

function loop($A) {
  $array1 = array();
  $num = (int)$A;
  if ($num == 0)
    $array1 = "0";
  for (int $i=0; $i<$num; $i++)
    foreach (loop($i-$num) as &$value)
      $array1[] = "+ ".$value." ";  //concat
  return $array1;
}

A literal translation of the above code into Haskell would be:

loop :: Int -> [String]
loop 0 = ["0"]
loop num = ["+ " ++ value ++ " " | i <- [0..num], value <- loop (i - num)]

It still doesn't achieve anything, but it does give you the flavour of Haskell's "loop"ing or iteration in list comprehensions.

First thing to notice is that the type signature loop :: Int -> [String] immediately alerted me to write loop 0 = ["0"] instead of loop 0 = "0" which would be more literally what you had, but Haskell has spotted that the output of loop would be inconsistent if it were sometimes a list of Strings and sometimes just a String. I think it's this kind of error checking it's worth learning about - maybe all the code you wrote when revising would compile in php, but because of the design inconsistencies, Haskell won't - it forces you to think clearly at writing time and fix bugs before compile time.

I'll explain my code, not as a full explanation of Haskell, but as a taster and relating it to your code:

loop :: Int -> [String]

loop is a function that takes an Integer and returns a list of Strings. Haskell won't let you use this with any other data type now, which means it's type safe, and you're protected from all sorts of nasty bugs straight out of the box. The type system is actually very flexible, expressive and powerful, and is one of the reasons we love Haskell, but here I'm using it to lock the function down.

(Lists are used widely in Haskell instead of arrays. They're very convenient and work fast for sequential access. There are array data types but they're less lovely/Haskellish - get used to lists first.)

loop 0 = ["0"]

This means if you call loop with the Int 0, it should return the list with one string, "0".

loop num = [ something | stuff... ]

Means you can get the values of your variables inside stuff and return them in something, so

loop num = [ "+ " ++ value ++ " " | stuff... ]

means we'll return (Haskell's version of) "+ ".$value." ". Here we use ++ instead of php's ..

i <- [0..num]

This means let i range from 0 to num. It has to be an Int because num is because loop :: Int -> ....

value <- loop (i - num)

This means let value range across the result of calling loop with the number i - num. value has to bee a String because loop :: Int -> [String].

In Haskell, it's like recursive calls are implemented as expression rewrites, so they disappear as they're called and don't clutter up the stack unless your calculation inherently clutters up the stack.

Putting it together gives:

loop num = ["+ " ++ value ++ " " | i <- [0..num], value <- loop (i - num)]

If that notation feels very weird, you might be more comfortable with more imperative style syntax:

loop :: Int -> [String]
loop 0 = ["0"]
loop num = do
    i <- [0..num]
    value <- loop (i - num)
    return ("+ " ++ value ++ " ")

Of course it still doesn't do anything useful but at least it's easy to keep track of.

Why not work through Learn You a Haskell for Great Good at http://learnyouahaskell.com/ or Real World Haskell at http://book.realworldhaskell.org/ both tutorials that start simple but go deep. I think you'll find Haskell a great way to write a small amount of correct code to replace a large amount of OK code. Think more clearly, write less!

Answer 2

It looks like you have some sort of dictionary. The typical Haskell data structure for a dictionary is a Map, provided by Data.Map. So if your keys are Strings and your values are Ints, then your Map would have type Map String Int.

Now, judging by your code, it seems you mix your keys and values in the same array, so first we have to separate them into key value pairs. I will pretend your starting input is a list instead of an array, although everything I'm writing here works perfectly fine for Haskell arrays, too:

fix :: [a] -> [(a, a)]
fix [] = []
fix [_] = []
fix (k:v:xs) = (k, v):fix xs

You can choose to stop there at an association list, in which case you could transform it into a list of descriptive strings:

describe :: (Show k, Show v) => [(k, v)] -> [String]
describe xs = map (\(k, v) -> "Stored On: " ++ show k ++ ", item: " ++ show v) xs

Or we could print them out directly:

printPairs :: (Show k, Show v) => [(k, v)] -> IO ()
printPairs xs = mapM_ putStrLn (describe xs)

Now, for more efficient lookups, you typically want to store the association list as a Map, so all you would use is the fromList function in Data.Map:

fromList :: Ord k => [(k, v)] -> Map k v

And any time you want to take the list back out of the map (i.e. to print it), you just use toList:

toList :: Map k v -> [(k, v)]