From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.text.pandoc/29177 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Ilia Zaihcuk Newsgroups: gmane.text.pandoc Subject: Re: Removing parts of the document with [walk] in Haskell Date: Sun, 5 Sep 2021 08:09:32 -0700 (PDT) Message-ID: <1473b62b-4b33-49b5-ac6d-52a5571d8068n@googlegroups.com> References: <915213fc-e4c4-480b-a6a2-fd3420777ddan@googlegroups.com> Reply-To: pandoc-discuss-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_4918_1039992972.1630854572893" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="18418"; mail-complaints-to="usenet@ciao.gmane.io" To: pandoc-discuss Original-X-From: pandoc-discuss+bncBD6IFBEKVAFBBLV32OEQMGQET6WQMBQ-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org Sun Sep 05 17:09:38 2021 Return-path: Envelope-to: gtp-pandoc-discuss@m.gmane-mx.org Original-Received: from mail-oo1-f59.google.com ([209.85.161.59]) by ciao.gmane.io with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1mMtm4-0004Zn-Ax for gtp-pandoc-discuss@m.gmane-mx.org; Sun, 05 Sep 2021 17:09:36 +0200 Original-Received: by mail-oo1-f59.google.com with SMTP id 68-20020a4a0d47000000b0028fe7302d04sf2915854oob.8 for ; Sun, 05 Sep 2021 08:09:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20210112; h=sender:date:from:to:message-id:in-reply-to:references:subject :mime-version:x-original-sender:reply-to:precedence:mailing-list :list-id:list-post:list-help:list-archive:list-subscribe :list-unsubscribe; bh=cybikIcNDsd3eFUwi6Vq1tbfGX0eFudxQaEVR+HLiUA=; b=FHBwIFQiqyCix/28IAEd1MeYRGzLm+Pnohi7S8pRsUtyvlJDS0xh86BxmH0SNGDS7Y vLxsUTe9obfjEByF7jkYChvx+UccnYC+mSl9Laj5Fkqaa5xtjAVTW9MPPsmf/CKvQZW9 HAfhxvNfPa/WODSm4c97a9GqAWAlGjZnxndrweuONzgmOqeBfChVUPm+6q1mUAVRh3aK 8RsD9MLrkUQ2I3fR7T3GbQ0MVLzsniKYSfaF19SL/gnhXqDT8+42qU3hnz9V61arqhVH Cjc5PaxlM5L9PTwyuCyS06P+mf96IEr4cd2jWmzsoRJR4dhYnXxkzV4LSOsat1noFw0u T4cw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=date:from:to:message-id:in-reply-to:references:subject:mime-version :x-original-sender:reply-to:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-subscribe:list-unsubscribe; bh=cybikIcNDsd3eFUwi6Vq1tbfGX0eFudxQaEVR+HLiUA=; b=D9ZwFgq8b3P6zlHqDm4dWURrnXjvFllaC6jZM8dxPSOx0rCyrmSh+OkEw2XY6I42Ql kbYHRz2R249EJx4LBXQhJwEZgh1U8ha1l1ngab8fwYkSPF3BJt0pXAiDTRy4NBhYnMbd TRLCtQ5vKOtrXdpRICug8z/EBALx9Ia/qoCDWcWThavcBsYRj9lknQsvenE352XTE524 X+oVZ4i9usfsuOBpGbhF1Hywkjd6dkYgs+burNnNx/DNJhq8J72drj7HFdW17OH6useC D2HhpuJAV8xIDY2xJAtZCgIuiSuR7l5VAKZ4lJ2jLZTZ4KTZ53Edlpry+iAB+e3X25Wo //kQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:date:from:to:message-id:in-reply-to :references:subject:mime-version:x-original-sender:reply-to :precedence:mailing-list:list-id:x-spam-checked-in-group:list-post :list-help:list-archive:list-subscribe:list-unsubscribe; bh=cybikIcNDsd3eFUwi6Vq1tbfGX0eFudxQaEVR+HLiUA=; b=lnBU8oUZ3wDuUtysFt6hVF2rvu2N7ZjLQ8b5or9JxQJQqIubrZJ1JGmI47Rp2+h/9A utOO46eJ6ftFTgtJCXrTQhNaGK1dvaJyegEluhc/V2iBkpl6do1RcfVZykx6eMlCVB7U NwlUEW9eWjiVRuB2vIguet2Z4eZm0FyogYoUVrXHLHVEYtNzc8c+TFbAY1JAAuNqsRA9 nEZFCPEmuVLVcFflaAtGs8pjlW1zaQ+jpQlFuOnY2cBN9N/ThmmmUFeX0mbFPywdJ/fE 1yD91+E0JI1ycoZLRpN2IRFu1xcnENqesdu7HlLtknyEAJBBGh0bNk855aCjNGDqhbWH p1tw== Original-Sender: pandoc-discuss-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org X-Gm-Message-State: AOAM530pW85eCQXUeQgltCIXwfN2hWvOTccJp2cDowFyNHNP5Xya13Nj XLd715esrUbSxxTCniqCikU= X-Google-Smtp-Source: ABdhPJzewKOzkRbmHVl3kW5LaPrI1pgZ2oDRq4t/7XOJ4Vf7lLcw3qJ1vRk+WepApU9tNImUUF9uEA== X-Received: by 2002:a05:6830:4084:: with SMTP id x4mr7403353ott.280.1630854575254; Sun, 05 Sep 2021 08:09:35 -0700 (PDT) X-BeenThere: pandoc-discuss-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org Original-Received: by 2002:a05:6830:1e87:: with SMTP id n7ls1127771otr.4.gmail; Sun, 05 Sep 2021 08:09:33 -0700 (PDT) X-Received: by 2002:a9d:4e98:: with SMTP id v24mr7726520otk.228.1630854573598; Sun, 05 Sep 2021 08:09:33 -0700 (PDT) In-Reply-To: X-Original-Sender: zoickx-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org Precedence: list Mailing-list: list pandoc-discuss-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org; contact pandoc-discuss+owners-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org List-ID: X-Google-Group-Id: 1007024079513 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , Xref: news.gmane.io gmane.text.pandoc:29177 Archived-At: ------=_Part_4918_1039992972.1630854572893 Content-Type: multipart/alternative; boundary="----=_Part_4919_244439712.1630854572893" ------=_Part_4919_244439712.1630854572893 Content-Type: text/plain; charset="UTF-8" Thanks for the detailed replies! The trick with using Span is neat, although it does seem more like a workaround than a true solution - it *is* making additional changes to the AST after all. Can I be sure that they won't influence my output in unexpected ways? (e.g. some obscure issue like auto-hyphenation in LaTeX, page breaks, etc.) @jgm, I don't really care about performance that much in my application, but I did do some benchmarking by your suggestion: here's a separate repo . This is actually my first ever encounter with the GHC profiler, so it's rather crude. Do let me know if you'd like any more info. TLDR: it does look like using the Span trick is more performant than concatMap (%time 0.8 vs 0.9), while the number of invocations of the base function (theFine in my original example) remains perfectly unchanged. @gwern *> If you do the concat trick, you start running into issues with how the `walk` operates exactly so it'll sometimes repeat operations or omit substitutions you expected to happen, and bottomUp/topDown sometimes cause issues like their own different omissions or just infinite loops (always fun).* This is scary! Correctness is certainly more important than speed. Do you have a concrete example where this issue occurs? If @jgm (the original author of pandoc!) is using this method and there are cases in which it behaves unexpectedly, this sounds worthy of an issue and/or a pull request on GitHub. On Sunday, September 5, 2021 at 8:23:19 AM UTC+3 John MacFarlane wrote: > > I have often used the method > > > allIsFine = walk $ concatMap theFine > > But I don't think this will be any more efficient than your > first version with `walk (filter $ not . isThe)`. > Actually, I'd be interested in seeing benchmarks with these > approaches, if efficiency matters enough to you to research > this more. > > Another possibility is to walk with a function like > > killThe :: Inline -> Inline > killThe (Str "the") = Str "" -- or: Span ("",[],[]) [] > killThe x = x > > This should be more efficient than the list versions, though > again it would be interesting to see benchmarks. > > > > Ilia Zaihcuk writes: > > > Hi all, > > > > Using pandoc-types' Walkable > > < > https://hackage.haskell.org/package/pandoc-types-1.22/docs/Text-Pandoc-Walk.html#t:Walkable> > > > class, what is the best-performing/most idiomatic way to filter out > certain > > elements from a document? > > > > Say I wanted to remove all occurrences of the word "the" from a Pandoc. > The > > best implementation I've been able to write for this is > > > > isThe :: Inline -> Bool > > isThe (Str "the") = True > > isThe _ = False > > > > removeThe :: Pandoc -> Pandoc > > removeThe = walk (filter $ not . isThe) > > > > Is this right? Does the use of filter here not mean an additional O(n) > > traversal happens on every list of Inlines? > > > > I feel like a better solution for this would be using > > > > filterThe :: Inline -> [Inline] > > filterThe (Str "the") = [] > > filterThe x = [x] > > > > or something similar, but of course > > > > removeThe = walk filterThe > > > > does not typecheck. We need a -> a, meaning [Inline] -> [Inline] here. > > > > > > The same question actually applies to any transformation which "changes > the > > number of elements": > > > > theFine :: Inline -> [Inline] > > theFine (Str "the") = [Str "the", Space, Str "fine"] > > theFine i = [i] > > > > allIsFine :: Pandoc -> Pandoc > > allIsFine = walk $ concatMap theFine > > > > Best, > > > > Ilia > > > > P.S. Sorry if this has been asked before. I feel it must be a common > issue, > > but all I've been able to find is this thread > > > > > with its links, which are 7 years old now and seem to be calling for > > changes in pandoc. Everything else suggests stepping outside Haskell. > > > > -- > > You received this message because you are subscribed to the Google > Groups "pandoc-discuss" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to pandoc-discus...-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org > > To view this discussion on the web visit > https://groups.google.com/d/msgid/pandoc-discuss/915213fc-e4c4-480b-a6a2-fd3420777ddan%40googlegroups.com > . > -- You received this message because you are subscribed to the Google Groups "pandoc-discuss" group. To unsubscribe from this group and stop receiving emails from it, send an email to pandoc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/Ez6ZCGd0@public.gmane.org To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/1473b62b-4b33-49b5-ac6d-52a5571d8068n%40googlegroups.com. ------=_Part_4919_244439712.1630854572893 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks for the detailed replies!

The trick wi= th using Span is neat, although it does seem more like a workaround than a = true solution - it is making additional changes to the AST after all= . Can I be sure that they won't influence my output in unexpected ways? (e.= g. some obscure issue like auto-hyphenation in LaTeX, page breaks, etc.)

@jgm, I don't really care about performance that= much in my application, but I did do some benchmarking by your suggestion:= here's a separate r= epo. This is actually my first ever encounter with the GHC profiler, so= it's rather crude. Do let me know if you'd like any more info. TLDR: it do= es look like using the Span trick is more performant than c= oncatMap (%time 0.8 vs 0.9), while the number of invocations of the = base function (theFine in my original example) remains perfectly unchanged.

@gwern
> <= /span>If you do the concat trick, you start running into issues with how the `walk` operates exactly so it'll sometimes repeat operations or omit substitutions you expected to happen, and bottomUp/topDown sometimes cause issues like their own different omissions or just infinite loops (always fun).
This is scary! Correctness is cert= ainly more important than speed. Do you have a concrete example where this = issue occurs? If @jgm (the original author of pandoc!) is using this method= and there are cases in which it behaves unexpectedly, this sounds worthy o= f an issue and/or a pull request on GitHub.
On Sunday, September 5, 2021 at 8:23:19 AM UTC+3 John MacFarlane wr= ote:

I have often used the method

> allIsFine =3D walk $ concatMap theFine

But I don't think this will be any more efficient than your
first version with `walk (filter $ not . isThe)`.
Actually, I'd be interested in seeing benchmarks with these
approaches, if efficiency matters enough to you to research
this more.

Another possibility is to walk with a function like

killThe :: Inline -> Inline
killThe (Str "the") =3D Str "" -- or: Span ("= ",[],[]) []
killThe x =3D x

This should be more efficient than the list versions, though
again it would be interesting to see benchmarks.



Ilia Zaihcuk <zoi...@gmai= l.com> writes:

> Hi all,
>
> Using pandoc-types' Walkable=20
> <https://hackage.haskell.org/package/pandoc-ty= pes-1.22/docs/Text-Pandoc-Walk.html#t:Walkable>=20
> class, what is the best-performing/most idiomatic way to filter ou= t certain=20
> elements from a document?
>
> Say I wanted to remove all occurrences of the word "the"= from a Pandoc. The=20
> best implementation I've been able to write for this is
>
> isThe :: Inline -> Bool=20
> isThe (Str "the") =3D True
> isThe _ =3D False
>
> removeThe :: Pandoc -> Pandoc
> removeThe =3D walk (filter $ not . isThe)
>
> Is this right? Does the use of filter here not mean an additional = O(n)=20
> traversal happens on every list of Inlines?
>
> I feel like a better solution for this would be using
>
> filterThe :: Inline -> [Inline]=20
> filterThe (Str "the") =3D []
> filterThe x =3D [x]
>
> or something similar, but of course
>
> removeThe =3D walk filterThe
>
> does not typecheck. We need a -> a, meaning [Inline] -> [Inl= ine] here.
>
>
> The same question actually applies to any transformation which &qu= ot;changes the=20
> number of elements":
>
> theFine :: Inline -> [Inline]=20
> theFine (Str "the") =3D [Str "the", Space, Str= "fine"]
> theFine i =3D [i]
>
> allIsFine :: Pandoc -> Pandoc
> allIsFine =3D walk $ concatMap theFine
>
> Best,
>
> Ilia
>
> P.S. Sorry if this has been asked before. I feel it must be a comm= on issue,=20
> but all I've been able to find is this thread=20
> <https://grou= ps.google.com/g/pandoc-discuss/c/idlbnOk1ooE/m/_QVvaRprHVcJ>=20
> with its links, which are 7 years old now and seem to be calling f= or=20
> changes in pandoc. Everything else suggests stepping outside Haske= ll.
>
> --=20
> You received this message because you are subscribed to the Google= Groups "pandoc-discuss" group.
> To unsubscribe from this group and stop receiving emails from it, = send an email to pandoc-discus..= .@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/pandoc-discuss/9152= 13fc-e4c4-480b-a6a2-fd3420777ddan%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups &= quot;pandoc-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to pand= oc-discuss+unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org.
To view this discussion on the web visit https://groups.google.com/d= /msgid/pandoc-discuss/1473b62b-4b33-49b5-ac6d-52a5571d8068n%40googlegroups.= com.
------=_Part_4919_244439712.1630854572893-- ------=_Part_4918_1039992972.1630854572893--