Złożoność łącznia list

Article View: pl.comp.lang.funkcyjne

Article #828

Back to pl.comp.lang.funkcyjne Previous Next

#828

From: Wojciech Muła
Date: Sat, 27 May 2006 13:02

15 lines
1555 bytes

Trochę się zdziwiłem, że w Ocamlu operator @ działa w czasie liniowym ze
względu na długość pierwszego argumentu.  Pogrzebałem trochę po Internecie 
i okazało się, że w zachwalanym tutaj Haskell jest tak samo.

Macie pomysł dlaczego tak jest?  Tzn. nie chodzi o sam algorytm łącznia,
którego dość łatwo się domyśleć, ale dlaczego nie implementuje się list
w taki sposób, żeby ich łącznie wykonywało się w stałym czasie -- przecież
dodatkowy koszt pamięciowy byłby niewielki.  Są jakieś poważniejsze
przeciwwskazania?

w.

-- 
Tępi głupcy są własnymi nieprzyjaciółmi, gdy dopuszczają
się złych uczynków, których owoce są gorzkie.

Technical Details

Message-ID: <slrne7gja7.2pp.wojciech_mula@cat.tac>

Path:

mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.nask.pl!news.nask.org.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mail

Show Full Headers

Complete Article Headers

Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.gazeta.pl!newsfeed.pionier.net.pl!news.nask.pl!news.nask.org.pl!newsfeed.tpinternet.pl!atlantis.news.tpi.pl!news.tpi.pl!not-for-mail
From: Wojciech Muła
 <wojciech_mula@poczta.null.onet.pl.invalid>
Newsgroups: pl.comp.lang.funkcyjne
Subject: Złożoność łącznia list
Date: Sat, 27 May 2006 13:02:00 +0000 (UTC)
Organization: http://www.mula.w.pl
Lines: 15
Message-ID: <slrne7gja7.2pp.wojciech_mula@cat.tac>
NNTP-Posting-Host: pb8.lancut.sdi.tpnet.pl
Mime-Version: 1.0
X-Trace: nemesis.news.tpi.pl 1148734920 27418 80.49.77.8 (27 May 2006 13:02:00 GMT)
X-Complaints-To: usenet@tpi.pl
NNTP-Posting-Date: Sat, 27 May 2006 13:02:00 +0000 (UTC)
User-Agent: slrn/0.9.8.1pl1 (Debian)
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit