
List fusion has existed for a long time (based on a change to the
internal representation of lists to make them streams).
IIRC the actual implementation was not considered a satisfactory
replacement for GHCs existing list implementation as performance
improvements were not uniform, the stream representation is good for
some things worse for others. I don't know whether this situation has
now changed.
Byte String and Text exist because implementing strings or byte
sequences as a cons list of Char or Byte is very inefficient both for
storage / data locality and for many operations. Fusion for Byte
String and Text is a bonus rather than a motivation.
[*] Stream Fusion: From Lists to Streams to Nothing at All
Duncan Coutts , Roman Leshchinskiy , Don Stewart
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401
On 17 April 2018 at 01:48, Steven Leiva
Interesting question.
So there is a concept in computer science called fusion.
My understanding (I don't have a CS degree) is that when data is subject to fusion, we don't create the intermediary lists as you are talking about. This is why, in Haskell, we have the ByteString and Text datatypes. Unlike String, they (ByteString / Text) are subject to fusion. Text is useful when we are dealing with unicode data, while ByteString is the correct tool when we are dealing with binary data.
All of this is to say that you should look at the ByteString data type. (Take a look at this description, for example: https://hackage.haskell.org/package/bytestring-0.10.8.2/docs/Data-ByteString...).
The only potential problem I see is that ByteString internally uses Word8, and since Word8 is unsigned, negatives are problematic. (Now that I think about it, how the heck do you represent negative numbers in binary?).
I hope this is useful.
On Sat, Apr 14, 2018 at 4:28 PM, Quentin Liu
wrote: Hi all,
Suppose I want to multiply two binary numbers whose representation uses lists (e.g. 14 is represented as [1, 1, 1, 0]). Is there any efficient way to do binary multiplication? The way I could come up with involves a lot of intermediate lists that will be discarded eventually and is extremely inefficient. I know one fast algorithm that uses Array but would it be possible to do the multiplication with only lists?
Regards, Qingbo Liu
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
-- Steven Leiva 305.528.6038 leiva.steven@gmail.com http://www.linkedin.com/in/stevenleiva
_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners