Lazy variants of isInfixOf and breakSubstring

[ryo1kato]

isSuffixOf available in Data.ByteString.Lazy, but not in Data.ByteString.Lazy.Char8 (it's commented out). Likewise isInfixOf is not available Data.ByteString.Lazy.

Similarly, there's no lazy version of breakSubstring

Is there any reason for this?

[dcoutts]

Exported isSuffixOf.

We lack implementations of isInfixOf and breakSubstring. We should probably get them from the stringsearch package.

[Bodigrim]

The relevant part of stringsearch: http://hackage.haskell.org/package/stringsearch-0.3.6.6/docs/Data-ByteString-Lazy-Search.html

[subterfugue]

What's the blocker here? I've just ran into this.

[Bodigrim]

@ribosomerocker No blockers, PRs welcome.

[subterfugue]

Am I correct in assuming that this depends on #307 ?
This would need to have a breakSubstring implementation used in the lazy substring module. Is it fine to continue with the current implementation?

[Bodigrim]

Not necessarily: it's likely better to have at least some (non-pathological) breakSubstring for lazy ByteString than none at all. Further refinements can be done separately.

[Equwece]

Hi, I am trying to add a lazy variant of breakSubstring from stringsearch to solve #100 and need an advice. The code from the stringsearch actively uses (1, 2) array package, but this package is not included in bytestring's build dependencies, what can be the preferred way to solve this problem (I suppose that adding new build dependency is not an option)?

[Bodigrim]

@Equwece you can use https://hackage.haskell.org/package/base-4.18.0.0/docs/Data-Array-Byte.html and low-level operations like https://hackage.haskell.org/package/base-4.18.0.0/docs/GHC-Exts.html#v:readIntArray-35-. You might end up implementing a small module with helper functions similar in spirit to https://hackage.haskell.org/package/text-2.0.2/docs/Data-Text-Array.html.

That said, I'd prototype with array package. If it works out well, you'll be able to migrate to low-level primitives later.

[Bodigrim]

I've been recently hit by the absense of lazy breakSubstring again.

A lazy way to implement breakSubstring for lazy ByteString is to adopt https://github.com/haskell/text/blob/master/src/Data/Text/Internal/Lazy/Search.hs. The algorithm in text has been well tested and well benchmarked, so it's a safe bet, given that it seems no one has much time to dedicate to this issue. @clyring what do you think?

[Equwece]

Sorry for the lack of progress on the task, I have implemented a lazy variant of breakSubstring using a self-written BoyerMoore implementation and byte array primitives similar to the text module (really appreciate @Bodigrim answer), but a quick benchmarking showed that my solution is much slower than stringsearch's solution, so I decided not to send pr yet and improve the implementation, but unfortunately I haven't found the time yet.