I am given a string in this form ppeeefpffeefe. Values:
Image that represents this string can be seen here: https://i.sstatic.net/GZppc.png
I am writing code in Haskell and trying to convert this representation into 1024 long list of integers where 1 represents the black (full) pixel and 0 represents white (empty) pixel assuming the image size is 32x32 pixels.
This is the code I have but Haskell is giving me trouble. I know that I need to keep track of how many parent nodes I have visited and update highest level that way. I am trying to take DFS approach but anything that will do a job will help.
getQuad :: String -> Int -> Int -> Int -> [Int] -> [Int]
getQuad tree level highestLevel pCount result | (node == 'p') = result ++ (getQuad (drop 1 tree) (level+1) level 0 result)
| (node == 'e') = result ++ (getQuad (drop 1 tree) level highestLevel pCount (result ++ (take (getAmount level) [0,0..])))
| (node == 'f') = result ++ (getQuad (drop 1 tree) level highestLevel pCount (result ++ (take (getAmount level) [1,1..])))
| otherwise = result
where
node = g
getNodeValue :: String -> Char
getNodeValue tree = if (length tree > 0) then tree !! 0 else 'x'
getAmount :: Int -> Int
getAmount l = 1024 `div` (4^l)
Thank you!
I think you're trying to do way too much in a single function. I recommend starting over, and explicitly introducing separate parsing phases (to convert your String to an ADT representing it) and production phases (to convert a value of the ADT to a list of Ints). For example, a suitable ADT might look like this:
data QuadTree = Parent QuadTree QuadTree QuadTree QuadTree
| Empty
| Full
deriving (Eq, Ord, Read, Show)
There are various techniques and libraries for parsing. Given your apparent level of expertise, and the simplicity of the format, I think I might recommend starting by writing the parser by hand and ignoring error-handling. Later you could think about learning about error-handling tools like Maybe or Either and parsing combinator libraries like parsec and friends to make it more flexible to changes in the language.
So, by hand and ignoring error-handling. Here's the skeleton I would put in place and try to fill out. Our parser needs to not just consume a String, but also be able to consume just part of a String and say what's left over: when handling a nested parent node, we need to return to the outer parent the chunk of the string that the inner parent didn't consume. So:
parseQuadTree :: String -> (String, QuadTree)
parseQuadTree ('p':rest) = -- TODO: exercise for the reader
parseQuadTree ('e':rest) = (rest, Empty)
parseQuadTree ('f':rest) = (rest, Full)
parseQuadTree other = error $ "parsing failed, expected a p, e, or f, but got " ++ other ++ " instead"
For example, we might expect the following ghci exchanges once we'd finished this function:
> parseQuadTree "e"
("", Empty)
> parseQuadTree "eef"
("ef", Empty)
> parseQuadTree "peeeeef"
("ef", QuadTree Empty Empty Empty Empty)
Once you have that, then I'd try to cook up a sensible representation of the 2d result. Perhaps a nested list would do:
type Image = [[Int]]
For example, you might interpret each element of the outer list as a row of the image; its elements are the columns of that row. The three basic operations you need for this thing are pasting images side-by-side horizontally and vertically and creating a blank image.
hcat, vcat :: Image -> Image -> Image
hcat = -- TODO: exercise for the reader
vcat = -- TODO: exercise for the reader
blank :: Int -> Int -> Int -> Image
blank w h pixel = -- TODO: exercise for the reader
-- OR, you could take just one size argument; we only ever need
-- square blank images in the following code
For example, you might expect these ghci exchanges once we'd finished implementing them:
> :set +m
> let x = [[0, 1]
| ,[2, 3]
| ]
| y = [[4, 5]
| ,[6, 7]
| ]
|
> hcat x y
[[0,1,4,5],[2,3,6,7]]
> vcat x y
[[0,1],[2,3],[4,5],[6,7]]
> blank 2 3 4
[[4,4],[4,4],[4,4]]
Now you can write a function which converts a QuadTree to an Image. We'll have to know how big the image is supposed to be, so let's make that an argument to the function.
renderQuadTree :: Int -> QuadTree -> Image
renderQuadTree size (Parent nw ne sw se) = -- TODO: exercise for the reader; use hcat and vcat
where subtreeSize = size `div` 2
renderQuadTree size Empty = blank size size 0
renderQuadTree size Full = blank size size 1
For example, we might expect some such exchanges at ghci once this is finished:
> renderQuadTree 2 Empty
[[0,0],[0,0]]
> renderQuadTree 2 Full
[[1,1],[1,1]]
> renderQuadTree 2 (Parent Empty Full Full Empty)
[[0,1],[1,0]]
> renderQuadTree 4 (Parent Empty (Parent Full Empty Empty Full) Empty Full)
[[0,0,1,0],[0,0,0,1],[0,0,1,1],[0,0,1,1]]
Finally we could make a top-level function that combines all these into one convenient piece.
getQuad :: String -> [Int]
getQuad s = case parseQuadTree s of
("", t) -> concat (renderQuadTree 32 t)
(s', _) -> error $ "parser did not consume the entire description string, leftovers are: " ++ s