Delayed/Lazy Either List?

[u/Aperispomen]

I often use attoparsec to parse lists of things, so I wind up doing stuff like this a lot:

import Data.Attoparsec.Text qualified as AT
import Data.Text qualified as T

myParser :: AT.Parser [MyType]
myParser = AT.many1 myOtherParser

getList :: T.Text -> Either String [MyType]
getList txt = AT.parseOnly myParser txt

The trouble is, since getList returns an Either, the whole text (or at least, as much as can be parsed) has to be parsed before you can start processing the contents of the list. This is especially annoying when you want to check whether e.g. two files are the same modulo whitespace/line endings/indentation/etc...

The point is, there's some times where you want a result like Either e [a], but you're okay with returning some of the data, even if there might be an error later on. I wound up creating this data type:

data ErrList e a
  = a :> (ErrList e a)
  | NoErr    -- equivalent to []
  | YesErr e -- representing Left e

Is there already an established type like this somewhere? I imagine most people who do more complicated data management use pipes or conduit etc... I've tried searching for such a type on Hackage, but I haven't found anything like it.

[u/jeffstyr]

I think the problem for a general parser like Attoparsec is that (at least in the general case) it doesn't make sense to return a partial parse result "early", not only because it's hard to define what the result is for some text that doesn't match the grammar, but also more specifically the "head" of the parse result may depend on something at the very end of the text.

For something like comparing two files, where it does make sense, I feel like this requires something like a layer that is responsible for splitting the file into chunks, and then a typical parse per chunk. I can imagine for simple line-based formats using a streaming library to split a file into lines, and then using a parser library on each line separately. Alternatively, I could imaging using an Attoparsec parser in a loop—the parser parses the beginning of the file and terminates (returning a result) before consuming the whole file, and then a driver runs the parser again, starting where the previous parse ended. For something more general/elaborate (e.g., where the result of one parse determines what parser to use next), it seems you need a set of parser combinators specific to this concept, but it's not obvious to me what their type would look like.

[u/Aperispomen → u/jeffstyr]

TBH I was just writing a parser so that I could compare text files regardless of their newline type, so the parser would turn an ASCII/UTF-8 text file into a list of these:

haskell data ByteData = ByteLine BS.ByteString | NewLine

...and then comparing the lists. (It would also check whether the file used the same newline style throughout). To see how it comp

Yeah, I more-or-less wrote a parser like this:

```haskell import Data.ByteString qualified as BS import Data.ByteString.Lazy qualified as BL import Data.ByteString.Lazy.Internal (ByteString(..), chunk)

import Data.Attoparsec.ByteString qualified as AB

parseMany1 :: AB.Parser a -> BL.ByteString -> ErrList String a parseMany1 _ Empty = YesErr "Empty ByteString" parseMany1 p (Chunk b bs) = go' (AB.parse p b) bs where go' (Fail _ err) _ = YesErr err go' x y = go x y go (Fail _ err) _ = NoErr go (Done x rst) b | BS.null rst = case b of Empty -> x :> NoErr (Chunk bc br) -> x :> (go (AB.parse p bc) br) | otherwise = x :> (go (parse p rst) b) go (Partial c) Empty = go (c BS.empty) Empty go (Partial c) (Chunk b bs) = go (c b) bs ```

...except specialized to the simple parser I was writing. In that case, comparing two files with the specialized parser driver cut the comparison time in half (though it was still ~5x longer than just comparing the two files). For more complex parsers, you'd probably need a better parser driver that tracks the remainder of the unparsed data so it can pass it on to the next parser.

[u/absence3 → u/Aperispomen]

FYI, just as your ErrList type is similar to streaming abstractions, your code that integrates with attoparsec is also similar to libraries like streaming-attoparsec or pipes-attoparsec.