-6
\$\begingroup\$

Your task will be to write a Haskell function that takes a list of integers and returns a sorted version of the same list. You are to do this without the use of builtins

What are builtins?

To keep ourselves from having to navigate edge case hell we are going to limit answers to Haskell (sorry if Haskell is not your favorite language). We are going to define a builtin as any named function that is not defined in your code. We are going to say that symbolic operators, (+), (:), etc. are not builtin functions. This applies both to prelude and any libraries that are imported.

What does it mean to use?

Before anyone tries to get smart with me, using a function is using a function. Whether or not the function is named in your source code is irrelevant (this is not ), if you make calls to the function without naming it that is also considered cheating. That being said calls to a function are not the only form of use, you shouldn't name a builtin function in your code even if you don't call it (I don't know why you would want to do that but I'm not taking any risks).

Scoring

This is so you should aim to do this in as few bytes as possible. However since different algorithms are not going to be competitive, (merge sort answers are probably going to be longer than insertion sort answers) I would like this to be considered a competition among individual algorithms, just as normal code golf is a competition among individual languages. For that reason I would like you to name your algorithm used in your header instead of the language. If you don't know the name feel free to put Unknown.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ Related (sort list without sort builtin) \$\endgroup\$
    – Okx
    Jul 8, 2017 at 14:35
  • 1
    \$\begingroup\$ I would have upvoted this if the challenge was not limited to a specific language. \$\endgroup\$
    – user41805
    Jul 8, 2017 at 15:14
  • \$\begingroup\$ @KritixiLithos I would have like to made it open to all languages, however the definition of builtin would have needed to be extremely complex. I figured it was best to constrain it to one language rather than have a broken challenge. Maybe I should have not asked the question. But I think its pretty fun if you give it a try. \$\endgroup\$
    – Wheat Wizard
    Jul 8, 2017 at 15:16
  • \$\begingroup\$ as we are talking about Haskell only, what about builtin values? \$\endgroup\$
    – nimi
    Jul 8, 2017 at 15:19
  • \$\begingroup\$ @WheatWizard Idea: allow other languages to join in but they are marked as NC \$\endgroup\$
    – user63187
    Jul 8, 2017 at 15:19

5 Answers 5

4
\$\begingroup\$

Haskell, 57 56 37 33 bytes

f l=[y|x<-[minBound..],y<-l,y==x]

Feed it with Ints, e.g. f [1::Int,2,3].

A port of my answer from the other sort without builtin challenge which supports also lists with repeated values.

Edit: @Ørjan Johansen saved 4 bytes. Thanks!

\$\endgroup\$
5
  • \$\begingroup\$ That fix is quite clever. \$\endgroup\$
    – Wheat Wizard
    Jul 8, 2017 at 15:44
  • \$\begingroup\$ @WheatWizard: it loops through all Ints, which takes some time. For a test you can go with f l=[-10..10]>>= \x->[y|y<-l,y==x] and limit the range of the element of the list to sort accordingly. -- or sort small values: f [-2^63+1::Int,-2^63,-2^63+1] \$\endgroup\$
    – nimi
    Jul 8, 2017 at 16:01
  • 1
    \$\begingroup\$ I see. Congratulations, It look like you have figure out a way to sort a list in O(n) :P \$\endgroup\$
    – Wheat Wizard
    Jul 8, 2017 at 16:05
  • 2
    \$\begingroup\$ This is 4 bytes shorter as a big list comprehension: f l=[y|x<-[minBound..],y<-l,y==x] \$\endgroup\$ Jul 8, 2017 at 19:49
  • \$\begingroup\$ @ØrjanJohansen: well spotted! Thanks a lot! \$\endgroup\$
    – nimi
    Jul 8, 2017 at 20:23
2
\$\begingroup\$

Mergesort, 110 bytes

x@(a:r)#y@(b:s)|a<b=a:r#y|1<3=b:x#s
r#s=r++s
(x:r)!(a,b)=r!(b,x:a)
_!t=t
s[x]=[x]
s l|(a,b)<-l!([],[])=s a#s b

Try it online! Example usage: s [4,1,26,-3,0,5].

# takes two sorted lists and merges them. ! splits a list in two sublists of equal length. s returns singleton lists unchanged because they are already sorted and sorts longer lists by splitting them in two parts, recursively sorts both and merges the resulting lists.

\$\endgroup\$
1
\$\begingroup\$

Insertion Sort, 44 bytes

s!(a:b)|a<s=a:s!b
s!x=s:x
f(a:x)=a!f x
f a=a

Try it online!

Since nimi has already outgolfed me I thought I would post the solution I came up with to my own challenge.

Explanation

Here we define a function (!) that takes a sorted list and inserts an element so that the list is still sorted.

s!(a:b)|a<s=a:s!b
s!x=s:x

We then define a function f that takes sieves the elements of a list into this function. (basically the equivalent of a foldr).

f(a:x)=a!f x
f a=a

Since the empty list is sorted, and each insertion keeps the list sorted, the end result is a sorted list with all the same items as the original. This algorithm is O(n2).

\$\endgroup\$
1
\$\begingroup\$

Quicksort (sort of), 44 bytes

s(h:t)=s[e|e<-t,e<=h]++h:s[e|e<-t,e>h]
s x=x

Try it online!

How it works:

s(h:t)=               -- let h be the head and t the rest of the input list
        [e|e<-t,e<=h] -- take all elements e from t that are less or equal than h
       s              -- and sort them recursively
          ++ h :      -- append h and append
        [e|e<-t,e>h]  -- all elements from t greater than h
       s              -- after sorting them
s x=x                 -- base case: if there's no first elemet, i.e. the list
                      -- is empty, the result is also the empty list
\$\endgroup\$
1
\$\begingroup\$

Here's a shorter merge sort, bottom up, called s. ((:[])<$>) divides up the list into singletons (turning "Joe" into ["J","o","e"]). d merges adjacent pairs of lists, using the basic merge function !. f iterates d until there's only one list.

Merge sort, 99 bytes

s=f.((:[])<$>)
a@(x:y)!b@(z:w)|x>z=z:a!w|0<1=x:y!b
a!b=a++b
d(x:y:z)=x!y:d z
d p=p
f[x]=x
f x=f$d x

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.