Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Re: Haskell triangular loop (correct use of (++)) (rohan sumant)
2. Re: Haskell triangular loop (correct use of (++)) (Silent Leaf)
3. Re: Haskell triangular loop (correct use of (++)) (Silent Leaf)
4. Type depending on value (Dmitriy Matrosov)
----------------------------------------------------------------------
Message: 1
Date: Mon, 11 Apr 2016 07:35:08 +0530
From: rohan sumant <r.s.sum...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Haskell triangular loop (correct use
of (++))
Message-ID:
<CAEHN=yyxdg4ubda6xw84i_qtbyycdwdgvruqzco05e1atl1...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
@Silent Leaf
I am indeed familiar with the list comprehension syntax indeed. I agree
with you that it certainly is the better alternative to writing handcrafted
functions especially when they involve (++). However the code you have
mentioned doesn't get the job done correctly. Your approach implements a
square nested loop which makes it at least twice as inefficient than the
one I am rooting for. The problem lies with the dropWhile function. It will
begin from the start of the list for every new (x,ix). This is particularly
bad in Haskell because the garbage collector cannot do away with
unnecessary prefixes of the input string, thereby wasting a lot of memory.
Rohan Sumant
On Sun, Apr 10, 2016 at 11:42 PM, Silent Leaf <silent.le...@gmail.com>
wrote:
> Dunno if that's what you're interested in, or if it's best in terms of
> efficiency, but there's syntax inside the language made just for this kind
> of thing, called list comprehension. It comes from math's definition of
> sets by comprehension, and since it's part of the language I'd have a
> tendency to trust its efficiency, but I might be entirely wrong on this
> aspect.
>
> Anyways, for your problem, say I want to create the set of pairs of your
> example:
>
> let result = [(x,y) | let xs = [1,2,3,0], (x,ix) <- zip xs [1,2..], y <-
> drop ix xs, x /= y]
> in result == [(1,2),(1,3),(1,0),(2,3),(2,0),(3,0)]
>
> Basically the syntax is: [ parameterized result element | conditions on
> the parameters]
> the conditions being a sequence of comma-separated items that are either:
> local variable declarations without the 'in', example being (let input =
> [1,2,3,0]), pattern-accepting generation of values from a list, or
> conditions on the parameters (here x and y).
>
> In order to build y's list I decided to zip xs with a list of indexes
> starting to 1, thereby ensuring no pair is twice in, considering the order
> doesn't matter.
> I'd bet the syntax is monad/do related, with all those right-to left
> arrows. Plus it fits the bill of what's actually happening here.
>
> Of course if you want a function, you can still write thereafter
> mkpairs :: Integral a => a -> [(a,a)]
> mkpairs n = [(x,y) | let xs = [1..n] ++ [0], (x,ix) <- zip xs [1,2..], y
> <- drop ix xs, x /= y]
>
> If you don't care about the order, I guess xs = [0..n] will be much more
> efficient, relatively speaking.
> Pretty sure the function even works for n == 0, since y <- drop 1 [0]
> won't have a thing to yield, hence, result = [].
>
> If that interests you:
> https://wiki.haskell.org/List_comprehension
>
>
> _______________________________________________
> Beginners mailing list
> Beginners@haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160411/88f511d1/attachment-0001.html>
------------------------------
Message: 2
Date: Mon, 11 Apr 2016 04:45:01 +0200
From: Silent Leaf <silent.le...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>,
r.s.sum...@gmail.com
Subject: Re: [Haskell-beginners] Haskell triangular loop (correct use
of (++))
Message-ID:
<CAGFccjMnvn70RgtJ+Bb3WZCVVU2UAoBwHn=7mscm0vxxnft...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Ah, from that I gather I probably won't think about anything you wouldn't,
then ^^
But I'll try because it's fun anyway!
If dropping incessantly from the start of the list at each iteration is the
problem (is that it? or did I not understand correctly?), could we not
manage the problem with memoization, using a recursive function of the like:
f 1 = drop 1 xs
f n = drop 1 (f (n-1))
I can't be sure at all, so I'll ask: would haskell remember the result of
each f 1, f 2, f 3, instead of recalculating them all the time? it would
allow for only one "drop" operation per iteration, and i guess it's the
best we can get with the general path I tried... but it seems obvious from
you both messages, there must be better ones no matter what, efficiently
speaking. :P
it could be naive, but one way to manage mere lists of integral numbers,
would be to transform them into one big number, and instead of dropping, we
do integral divisions/recuperation of remainders. i bet *if* that's more
efficient, there's a library to do that already.
one only has to to write the number that serves as list as a juxtaposition
of n-sized clusters of digits, n being the biggest power of ten reached by
the biggest number of the list. smaller numbers, tha have not enough digits
could be written with zeroes to fill in the rest: "0010" for example, and
of course so as to not lose trailing zeroes of the number at the leftest,
one has to start (from the right) with the smaller numbers:
123...010...002001.
But who knows if it's really more efficient? I'd have a tendency to say,
arithmetic is just numbers, the computer can do it way quicker and with
much less memory, but maybe not.
Just an idea off the top of my head. I bet no matter the technique we use,
handling one big number could end up being faster than a big list, and with
the right set of functions, it could be just as easy, but i could be
totally wrong.
And if too big numbers are problematic, we can still attempt intermediary
solutions, like lists of clustered numbers ^^
Sorry for the stupid ideas, hopefully soon my wild imagination will be
better handled by what i'll learn when i get a little less newbie. :P
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160411/0d62a72f/attachment-0001.html>
------------------------------
Message: 3
Date: Mon, 11 Apr 2016 07:06:21 +0200
From: Silent Leaf <silent.le...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] Haskell triangular loop (correct use
of (++))
Message-ID:
<cagfccjpaqrgyot30w4p3avmdjaayqcfptetx6bcjbxfap_q...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
I'm sorry to hear, no implicit memoization (but then is there an explicit
approach?). in a pure language, this seems hardly logical, considering the
functional "to one output always the same result" and the language's
propensity to use recursion that uses then previous values already
calculated. Really hope for an explicit memoization! and i don't mean a
manual one ^^ if that is even possible?
Anyway, i just don't get your function f. you did get that in mine, xs was
the value of my comprehension list, aka [.s1..n] ++ [0]
>From there, if I'm not wrong, your function creates a list of all truncated
lists, I supposed to be used with a call for the nth element? True, it
memorizes all needed things, and in theory only "drops" once per element of
the list.
As for incorporating it, i'm thinking, local variable? ^^ the function
itself could be outside the comprehension list, in a let or where, or
completely out of everything, I don't really see the problem. then it's
just a matter of it being called onto xs inside the comprehension list,
like that:
result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, (x,i) <- zip xs
[1,2..], y <- yss !! i, x /= y]
The remaining possible issue is the call to !!... dunno if that's costy or
not.
The best way to go through the list I suppose would be by recursion... oh
wait, I'm writing as I'm thinking, and I'm thinking:
result = [(x,y) | let xs = [1,2,3,0], let yss = f xs, x <- xs, ys <- yss, y
<- ys, x /= y]
after all, why not use the invisible internal recursion? What do you think?
As for the number-instead-of-number-list, the crucial point i mentioned was
to determine the maximum number of digit (biggest power of ten reached),
and fill up the holes of the smaller numbers with zeroes, so your examples
would be:
[1,2,3] = 123 --maximum size of a number = 1, no need to fill up
[12,3] = 1203 --maximum size of a number = 2 digits, thus the hole beside 3
gets filled with a zero, just like on good old digital watches ^^
Do you think extraction of clusters of digits from numbers would be
advantageous, efficiently speaking?
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160411/6acc2498/attachment-0001.html>
------------------------------
Message: 4
Date: Mon, 11 Apr 2016 14:32:30 +0300
From: Dmitriy Matrosov <sgf....@gmail.com>
To: beginners@haskell.org
Subject: [Haskell-beginners] Type depending on value
Message-ID:
<cafdvufmg-0umskw9b8opumd1hc_mnqqha6qe_xwhyg00-az...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
> {-# LANGUAGE DataKinds, KindSignatures, GADTs, StandaloneDeriving #-}
Hi.
Here is natural numbers and its singleton definition, which i take from
"Part
I: Dependent Types in Haskell" article by Hiromi ISHII [1]:
> data Nat = Z | S Nat
> deriving (Show)
>
> data SNat :: Nat -> * where
> SZ :: SNat 'Z
> SN :: SNat n -> SNat ('S n)
> deriving instance Show (SNat n)
But i can't figure out how may i define function returning SNat value
depending on Nat value:
f :: Nat -> SNat n
f Z = SZ
f (S n) = SN (f n)
This does not typecheck, because, as i understand, ghc can't infer type n.
Is
it possible to do this at all?
[1]:
https://www.schoolofhaskell.com/user/konn/prove-your-haskell-for-great-safety/dependent-types-in-haskell#ordinals
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160411/19222f45/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 94, Issue 7
****************************************
