Thank you Stephen for the clarification! On Wed, Apr 18, 2018 at 12:33 PM, Stephen Tetley wrote:

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 wrote:

...

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.html#t: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

_______________________________________________ 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