Wednesday, August 13, 2008

Using Difference Lists

I posted my enthusiasm about difference lists for Haskell earlier this month, but then became sidetracked by combinators and reading lists, so, let's get back on track.

Difference lists are a (very) useful data structure in Prolog, particularly when it comes to parsing with definite clause grammars (DCGs) and when it comes to list construction (again, using DCGs). Why? Well, to answer that question, let's examine the structure of difference lists. The Prolog (or relational) representation of a difference list is of the form:
X = [1,2,3|Y] - Y
What that relation describes is that X is the difference of the pair of lists of (first) [1,2,3] appended with the list Y minus (second) the list Y.

Well, what is the value of the list Y? To a Prologian, this question is not important (for Y, being a logic variable, can be any list or, even, not a list at all because the variable is still uninstantiated (a "free" variable)). Its importance is that it gives us an "instant" index into the list after the elements we've already processed. The significance of that index for parsing is that we now have a stream over the parsed (list) data, which gives us the ability to translate BNF grammars directly into working parsers. The significance for list construction is that we "simply" walk "backward" through the DCG to construct a list from a (parsed) internal representation, without paying the linear cost of either (a) traversing the list each time to add a new element (which results in exponential time list construction) or (b) building the list in reverse (adding new elements to the head of the list) and then applying reverse to the end result.

"Big deal!" you scoff, "zippers [also called 'finger trees'] already give us indices into data structures. Who needs a funny-looking specialized zipper just for lists?"

"Good point!" is my response. Zippers are powerful and flexible data structures that not only provide that index over any data structure, but, even better than difference list's index that only goes forward (with any dignity) in constant time, the zipper's index can go both forward and backward through that (generic) structure in constant time. So, if you are not familiar with zippers, I request that you run, don't walk, to a good overview to learn more about their utility.

With all their flexibility and power, in certain situations, a zipper is not the correct choice for some list processing tasks; the difference list's simplicity shines in these situations. First, for the unidirectional index of the difference list (it moves forward through the list well, but backwards ... not so much), this, for list construction purposes, is hardly ever an issue, and if it becomes one, then backtracking is easily installed with some MonadPlus magic. Next, you, the coder, are responsible for constructing a zipper list data type each time you need one, but Don Stewart has provided Data.DList; no construction necessary! Last, an example structure of a zipper list, for the list a++b is (reverse a,b), so if we wish to reconstruct the original list, for an a of large magnitude, we still pay the linear (reverse) cost in reconstruction as well as the linear cost of appending b to that result.

You heard it here first, folks — difference lists: [zipper lists] can't touch this!

Okay, I've finished throwing it down for now. Let's look at difference lists from the Haskell perspective and then use this data structure in a list construction example.
> import Data.DList
For my examples, I'm going to be looking at the subset of difference lists that I can compare and see:
> instance Eq a => Eq (DList a) where
> x == y = toList x == toList y

> instance (Eq a, Show a) => Show (DList a) where
> show x | x == empty = "\\x -> [x]"
> | otherwise = "\\x -> [" ++ show (head x)
> ++ doShow (toList (tail x)) ++ ":x]"
> where doShow [] = ""
> doShow (a:b) = ", " ++ show a ++ doShow b
With the above instance declarations, we see that
(singleton 1) `snoc` 2 `snoc` 3
gives us the representation
λ x . [1, 2, 3:x]
... snoc appends an element to the end of a list (so it's the reverse of cons).

Prologians are always smug with their ability to create an infinite stream of 1s with X = [1|X]. And, no doubt about it, Prolog is a programming language that makes list construction easy ... *ahem* almost as easy as list construction in Haskell ("Your list comprehensions outshine even Prolog for sure..."):
repeat 1
[1,1..]
... and now with difference lists ...
let x = unDL (singleton 1) x in x
But no self-respecting Prologian would freeze their interpreter with a such a rash proof; Haskellians have no such concern, thanks to weak head normal form:
take 5 (repeat 1)
So there!

Let's examine an application of difference lists. I have a little scanner that I use to help me in my oration. The meat of the algorithm (before difference lists) was as follows:
> lettersIn word = lettersIn' word []

> lettersIn' [] ans = reverse ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (h:ans)
> | otherwise = reverse ans
Ugh, yes, reverses galore! This is an oft-recurring pattern in Haskell code that is very easily fixed with some difference list magic:
> lettersIn word = lettersIn' word empty

> lettersIn' [] ans = toList ans
> lettersIn' (h:t) ans | isLetter h = lettersIn' t (ans `snoc` h)
> | otherwise = toList ans
A very simply example, I grant you, for if we take a list whose elements are all in the set of the alphabet, the above code is a very complicated way of reinventing the id function. Or, put another way, who's going to teach me about scanl? Hm, would I be required to use the continuation Monad to escape the scan, I wonder? But you get the general idea for list construction, right? Instead of building the list by adding to the head ("cons"ing) and then applying reverse to the result, the different list allows one to "snoc" each element and return the correctly ordered result. For a single list construction, the benefit may not be all that obvious, but when one builds, e.g., an XML generator for a complex internal representation, reversing the reverse of the reversed reversed child element becomes an odious labour — difference lists eliminate all the internal juggling, replacing that complication with a straightforward constant-time list and element in-place append.

So, next time you need to do some list construction, instead of falling back on the reverse standby, flex your new difference list muscles; you'll be pleasantly surprised.

57 comments:

David R. MacIver said...

"zippers [also called 'finger trees']"

Um. No they're not. A finger tree is a totally different data structure to a zipper. A zipper is a view into another data structure with a "special point" in that structure. A finger tree is an tree designed for sequences with fast concat, append and prepend.

Zipper: http://en.wikipedia.org/wiki/Zipper_(data_structure)

Finger tree: http://en.wikipedia.org/wiki/Finger_tree

meteficha said...

I wonder why you didn't write

lettersIn (x:xs) | isLetter x = x : lettersIn xs
lettersIn _ = []

meteficha said...

Or even better:

lettersIn = takeWhile isLetter

Jim Apple said...

David R. MacIver:

Yes, finger trees aren't the same as zippers, but zippers are really just fingers. Finger trees could have been called zipper trees if Kaplan & Tarjan hadn't gotten there first. Their fingers are actually special points in trees, along with a path from those points to the root, just like a zipper!

Jim Apple said...

I like difference lists. However, I think anything you can do with a difference list you can do with constant-time-append deques, which provide other operations as well:

Kaplan & Tarjan's simpler real-time version
Okasaki's amortized-time version

Chris Rathman said...

Might be worth noting that the book Concepts, Techniques, and Models of Computer Programming has a nice explanation of Difference Lists using Oz in section 3.4.4. I translated the code to Alice ML, where futures can used to get the same effect.

Chris Rathman said...
This comment has been removed by the author.
Pseudonym said...

Prologians are always smug with their ability to create an infinite stream of 1s with X = [1|X].

Yes, because breaking the logical interpretation of unification is a virtue in logic programming.

(Actually, I think that Prologians are secretly happy every time they come up with a way to do anything at all in Prolog. I digress.)

What I actually wanted to say was that I found it amusing that you used "show" rather than "shows" in an article about difference lists.

Juliana Kho said...

http://www.play1628club.com/
http://www.blue338.com/
http://www.register-osg777.org/
http://www.daftarsv88.com/

JADUL
http://www.suitjari.com/

LB
http://www.aduayam128.net/
http://www.judi-ikan.net/
http://www.daftarpoker-online.net/

OSG TOTO
http://www.oglokidn.net/
http://www.daftarrouletteidn.com/

Juliana Kho said...

http://gwc388.org/

Juliana Kho said...

http://www.dadu-koprok.com/
http://www.judidadu-online.com/
http://www.registertotomacau.com/
http://www.pengecertogel.com/

REMI
http://www.situsdomino.biz/

YKB
http://143.95.145.143/
http://www.loginigkbet.net/
http://www.downloaddaninstalljoker123android.com/
http://www.slotbalidream.com/
http://www.daftarslotbalidream.com/

Juliana Kho said...

http://www.downloadjoker88.com/

Anonymous said...

https://panasoniclampung.blogspot.com/
https://servicecentersamsungbandarlampung.blogspot.com/
https://servicehuaweicenter.blogspot.com/
https://serviceiphonelampung.blogspot.com/
https://servicecenteriphone.blogspot.com/
https://servicecentervivo.blogspot.com/
https://servicecenteroppo.blogspot.com/
https://servicecenterxiaomi.blogspot.com/
www.lampungservice.com
https://servicecenteraxioo.blogspot.com/

Anonymous said...

https://jskursus.blogspot.com
https://jasaeditfotobandarlampung.blogspot.com
http://www.lampungservice.com
https://tempatservicehpdibandarlampung.blogspot.com
https://jalanbumisarinatar.blogspot.com
https://kursusservicehplampung.blogspot.com
https://makalahbiz.blogspot.com
https://cellularlampung.blogspot.com

lnwMashow45 said...

Thank you for watching สมัคร SBOBET

JannethManalu said...
This comment has been removed by the author.
Caroline Wijaya said...

Permainan Sabung Ayam tentunya sudah pada tahu ya, yang dimana ayam melawan ayam pertandingan yang sangat seru ini bisa kalian nonton secara live lohh, banyak yang bermain di situs kami dan merasa sangat nyaman, bagi kalian yang ingin bermain bisa kunjungi situs kami, dijamin kalian akan merasa sangat senang.

keuntungan daftar sv388

bonus sv388


cara login sv388 di ios

operator login sv388

panduan login sv388


agen sv388 deposit pulsa

deposit sv388 via telkomsel

deposit sv388 via xl

deposit sv388 ovo

deposit sv388 dana

deposit sv388 linkaja

deposit sabung ayam online pulsa

deposil pulsa sv388


aplikasi sv388 versi terbaru

cara download sv388

cara download aplikasi sv388

download aplikasi sv388

download sv388 android

download sv388 ios

cara install sv388

download aplikasi sabung ayam


withdraw akun sv388

cara withdraw sv388

cara withdraw akun sv388

keuntungan withdraw sv388

minimal withdraw sv388

syarat withdraw sv388


operator sv388

live chat operator sv388

Lince Lin said...

yuk, join game berkualitas bagus dan terpercaya hanya di:

Bola: Daftar
Poker: Daftar
Slot: Daftar

Kami memberikan BUKTI bukan JANJI

jasa website gembling said...

JudiKartu adalah agent taruhan online terpercaya

JudiKartu adalah agent taruhan bola Jadwal Bola terpercaya pertama di Indonesia yang menyediakan layanan live bakarat, roulette, dan sicbo online. Memberi kepuasan pelanggan dan melayani lebih baik dari yang lain.
Taruhan online, Judi Online, Agen Casino, dan Agen Bola yang telah terbukti terpercaya. Dengan proses deposit dan withdraw cepat. Pelayanan taruhan online terbaik dengan team support yang profesional. Selalu siap untuk menjawab pertanyaan anda 24 jam sehari, dan 7 hari seminggu. JudiKartu tidak Pernah Libur, selalu ada untuk melayani anda.
agen bola

poker online
poker uang asli


jasa seo indonesia

dominoqq
bandarqq
poker qq online
pkv games

prediksi bola
jadwal bola
agen bola

sylas ct said...

aphelios ct
Sylas Ct
Lucian Ct
sett ct

Dubaiboy45 said...

ผลบอลเมื่อคืน ข่าวฟุตบอล

Dubaiboy45 said...

เกมออนไลน์

jenny said...

togel online
bandar togel terpercaya
agen togel
judi togel

Deriiin said...

Daftar Live22

Register Live22

Live22 Register

Live22 Indonesia

Agen Live22 Indonesia

Daftar Akun Live22

Daftar Slot Live22

Daftar Live22 Slot

Daftar Live22 Casino

ID Live22 Indonesia

Slot Live22

Live22 Slot

Agen Live22 Deposit 25 Ribu

Agen Live22

bandarq228 said...

mainkan pkv games di situs terbaik bandarq228 dan raih bonus hingga ratusan juta untuk membantu ekonomi anda di tengah pandemi ini
daftarkan diri anda sekarang juga di http://180.215.13.119/

Situs Poker Online said...

kami merupakan bandarqq dan dominoqq yang siap membantu anda untuk mencapai impian yang anda inginkan. temukan di sini https://dominoqqme.com/

barakcasino said...

judi bola online terbaik dan terpercaya. memiliki provider terbesar asia dan sudah menjadi agen judi casino online resmi dan memiliki ijin dan pengawasan dari badan pengawasan perjudian online http://149.28.153.153/

dfgfhft said...

baginda4d merupakan bandar slot online terpercaya joker123 yang memberi peluang kemenangan terbaik http://139.180.184.251/

hasilbola said...

https://hasilbola.live/prediksi-sepakbola/baca/5481/west-ham-vs-brighton-27-desember-2020

Prediksi Bola West Ham vs Brighton 27 Desember 2020 yang akan diselenggarakan langsung Olympic Stadium.

Dalam pertemuan kedua tim di Liga Inggris kali ini. Akan di Jadwal Bola Malam Ini pada hari Minggu, 27 Desember 2020 pada pukul 21:15 WIB.

Dalam Prediksi Bola kali ini kita mengupdatekan paling banyak karena akan mengadakan tahun baru, maka dari itu hasilbola.live akan memberikan Tips Prediksi Bola Jitu.

Unknown said...

Di mana Anda akan mendapat masalah dengan poker online adalah jika Anda benar-benar memulai situs poker online di mana pemain dapat bermain online dengan uang sungguhan. Dalam hal ini, Anda akan mendapatkan berbagai macam masalah. Negara bagian menyukai monopoli mereka pada permainan sehingga Anda dapat yakin bahwa mereka akan menuntut Anda jika Anda mencoba memulai situs poker atau mengadakan permainan bandarqq bawah tanah.
http://180.215.200.101/

Doyan303 Slot Online said...

Slot online pragmatig dan spadegaming dangat populer di indonesia. http://149.28.158.118/

togelonline said...

judi slot online joker123 di bandar togel online barak4d lebih banyak mendapatkan freespin. yok gabung dan buktikan sendiri. kunjungi kami di http://149.28.142.155/

mega888 said...

sertai slot online kasino mega888 rasmi, kemenangan anda akan dibayar tanpa sebarang potongan http://mega888user.com

Keluaran Hongkong said...

situs keluaran hongkong menjadi agen judi online terbesar http://keluaranhongkong88.com/

keluaran sgp said...

salam jackpot dari kami salah satu situs togel online terpercaya di Indonesia http://keluaransgp88.com/

Pengeluaran SGP said...

Kami tidak akan mengibuli para pemain toto sgp yang mengunjungi http://pengeluaransgp88.com , semua data pengeluaran sgp dijamin benar

hkpools said...

jackpot terbanyak di hkpools
ayo segera daftar disini.

Bandar Togel Online said...

situs bandar togel online CASTLETOTO mempunyai banyak akses yang dapat anda temukan dipencarian database manapun http://128.199.187.54/

JOKER123 SITUS JUDI SLOT ONLINE RESMI said...

Thank you for presenting an interesting website to read, I like this site because it has interesting and relevant content. Therefore, keep writing so that everyone can read. popslot22
popslot22
popslot22
popslot22
popslot22
popslot22
situs slot terpercaya
http://167.172.6.6/

castletoto said...

Agen Togel Online paling terpercaya dan amanahhh hanya di kingdom grup

Slot Online KINGDOM said...

Slot Online KINGDOMGRUP jangan lewatkan pragmaticnya

Bandar Togel Online said...

Pragmatic Play

Unknown said...

http://170.187.227.99/
bergabunglah di dominoqq...

mposlot said...

Pastikan anda bergabung di Laskar MPO yang merupakan situs terbaik di Indonesia resmi dan terpercaya yang sangat berpengalaman dalam menghadirkan permainan terbaik untuk anda. http://139.162.43.253/

Unknown said...

bergabunglah di situs web dominoqq..
http://170.187.227.99/

mposlot said...

http://139.162.43.253/

ye.. akhirnya bonus deposit tanpa potongan..
mari bergabunglah...

slotgacorbcaplay said...

slot paling aw aw hanya di bcaplay
slot gacor online indonesia

PG Soft Games said...

aw aw PG Soft 88

pokerbola said...

serunya bermain di situs pokerbola.

http://149.28.143.94/

PG Soft 123 said...

i want to sleep Pragmatic 88

bola online said...

pastikan anda bergabung di situs resmi taruhan bola online resmi dan terpercaya dengan rating kemenangan tertinggi http://45.76.158.166/

HOKQBET said...


Slot deposit pulsa tanpa potongan sangat diminati oleh banyak orang, karena tidak semua situs memiliki deposit pulsa tanpa potongan sehingga ini menjadi unggulan terhadap situs kami yang menawarkan promo deposit pulsa tanpa potongan agar para pemain dapat bermain dengan seluruh uangnya tanpa harus potong biaya admin.

pasti200m said...

ini lah yang di sebut online daftar slot online via dana terpercaya

slotdepositdana99 said...

this is what we say no more live link situs slot online pakai dana

Unknown said...

menjadi yang terbaru saat ini pasti200m slot

AUTOJP4D said...

Data prediksi terlengkap hanya bisa anda dapatkan di https://autojp4d.com/

Jayatogel said...

slot88
togel
slot88
situs slot terbaru