CODEWITHSUNDEEP
haskell
slemoine
slemoine

Reputation: 367

String ordering using fold

I'm a newbie in haskell and start to write my first small program.

The purpose: The app asks the user to input items for some categories. All inputs are stored in a Map Category [Item] (or Map String [String]). Once all categories has been fulfilled, the map is written to a file.

import qualified Data.Map as Map

type InputLine = IO [String]

type ItemsRegistry = Map.Map String InputLine

--main = do sequence . printValues . getInput $ ["head", "body"]

main = do
  writeFile "data.txt" ""
  putStrLn "Write the word \"stop\" to end the input"
  sequence . writeData "data.txt" . getInput $ ["B", "A"]

getInput :: [String] -> ItemsRegistry
getInput cat = foldl (\acc category -> Map.insert category (insertCategory category) acc) Map.empty cat

insertCategory :: String -> InputLine
insertCategory category = do
  putStrLn $ "Add items for category " ++ category
  insertItem []

insertItem :: [String] -> InputLine
insertItem values = do
  x <- getLine
  case x of "stop" -> return values
            x -> insertItem (x:values)

writeData ::  String -> ItemsRegistry -> [IO ()]
writeData path data_ = [ writeLine path k (Map.lookup k data_) |  k <- Map.keys data_ ]

-- filepath category lineOfItems
writeLine :: String -> String -> Maybe InputLine -> IO ()
writeLine path category (Just line) = line >>= (\words -> appendFile path $ formatLine category (unwords words))  
writeLine path category Nothing = return ()

formatLine :: String -> String -> String
formatLine category items = category ++ " " ++ items ++ "\n"

--printValues :: ItemsRegistry -> [IO ()]
--printValues l = [ v >>= putStrLn . show | (k,v) <- Map.toList l]

When running the above I can't figure out why it asks me for input category A before B since I used a foldl ? Seems like there is some lexical ordering behind it but I can't understand why.

Thanks

Upvotes: 0

Views: 179

Answers (2)

HTNW
HTNW

Reputation: 29193

Maps are ordered. That's why most of the functions that work on Map k vs have a Ord k constraint. I think, internally, they are kept as some sort of binary tree. There is no reordering of execution, just reordering of data. If you want a "map-like" structure that stays in the order you want rather than being sorted, use association lists:

type Assoc k v = [(k, v)]
-- usually we don't use this alias; [(k, v)] is shorter and widely understood

In Prelude, you will find

lookup :: Eq a => k -> [(k, v)] -> Maybe v

and all other map-like operations can be implemented through basic list manipulation.

In your code, you should thus change:

type ItemRegistry = [(String, InputLine)]

Also, if you use foldl to write some function from lists to lists, it will reverse the order, generally. This is because

foldl c n [x, y, z] = c (foldl c n [x, y]) z

which says to do something with the last element before doing something with the rest of the list, while

foldr c n [x, y, z] = c x (foldr c n [x, y])

means to do something with the first element before processing the rest. If you are used to strict languages, this is backwards. In a lazy language, things on the "outside" of an expression "happen" first; in a strict language things on the "inside" happen first.

This was not a problem for Map, because Map.insert is unordered (as long as there are no duplicate keys); it doesn't matter in what order you insert keys into a Map, because the Map will always be sorted according to the Ord instance. It is, however, a problem for association lists, which preserve order. You should thus say:

getInput :: [String] -> ItemsRegistry
-- getInput = foldr (\category acc -> (category, insertCategory category) : acc) []
-- but that should really be
getInput = map (\category -> (category, insertCategory category))
-- which you can turn into
-- getInput = map ((,) <*> insertCategory)
-- if you want

Finally, your writeLine and writeData are questionable. Notice:

writeData path data_ = [ writeLine path k (Map.lookup k data_) |  k <- Map.keys data_ ]

k is definitely a key to data_, but Map.lookup k data_ :: Maybe InputLine. Why? It won't ever be Nothing. The same would happen for Data.List.lookup. This means you've done something wrong, and I'm sure it made you uncomfortable when you saw it, too. I see you band-aided it by making writeLine accept a Maybe, making it a no-op if it receives Nothing, but that's just dodgy.

If you were using Map (which you can't, really, as I've said), you would use this function, which turns a Map into an association list.

-- alias toAscList
Data.Map.assocs :: Map k a -> [(k, a)]

And you would say

writeData path data_ = [ writeLine path k v | (k, v) <- assocs data_ ]

(If you think this look inefficient, it isn't. The documentation for assocs says it is subject to list fusion, meaning that the intermediate assocs data_ list that appears to be created here gets optimized out of existence.)

Of course, we already have an association list. This makes writeData even simpler:

-- do be careful; Map.insert clobbers duplicates, but (:)ing onto an association
-- list means duplicate keys are preserved
-- you'd need to run nubBy ((==) `on` fst) on data if that's an issue
-- *that* might be inefficient (O(n^2) in the length of data_)
writeData path data_ = [ writeLine path k v | (k, v) <- data_ ]
-- or even
-- writeData path = map (uncurry (writeLine path))
-- if you want to be confusing
-- writeData = map . uncurry . writeLine

writeLine :: String -> String -> InputLine -> IO ()
writeLine path category lines = do words <- lines
                                   appendFile path $ formatLine category $ unwords words

Upvotes: 1

Robin Zigmond
Robin Zigmond

Reputation: 18249

According to the docs for Data.Map, Map.keys returns "all keys of the map in ascending order". (Recall that the Map type requires its keys to be of a type that's an instance of Ord.)

Since "A" comes before "B" in the natural order, I think your use of Map.keys is causing writeData to have the "ask for A" action before the "ask for B" one.

Upvotes: 2

Related Questions