Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to sort a list in Haskell in command line ghci

I am new to Haskell, and I want to make 1 function that will take two lists and merge then together, and then sort the combined list from smallest to biggest. this should be done in the command line without using modules.

This is what i currently have, I am having trouble getting the "sortList" function to work, and also I do not know how to combine these 3 lines into 1 function.

let combineList xs ys = xs++ys
let zs = combineList xs ys
let sortList (z:zs) = if (head zs) < z then (zs:z) else (z:(sortList zs))
like image 664
Iceandele Avatar asked Sep 29 '13 20:09

Iceandele


People also ask

How to sort a list in Haskell?

The sort function sorts the elements of the given list in ascending order and returns it as a new list. The sort function is available in Data. List module which must be imported in our program to make use of sort function. The internal implementation of the sort function is merge sort. Let us discuss examples of Haskell Sort.

How do I create a sort function in GHCi?

It's a bit awkward to define a sorting function within the ghci. I thing the easiest way to do it would be to write the sorting function in a file, and then loading it into ghci. For instance, you could write this concise (though not in-place!) version of quicksort in a file called sort.hs (taken from the HaskellWiki ):

What are the different types of commands in Haskell?

:seti – Like :set, but only affects commands typed at the GHCi prompt, not those loaded from a file. :show language – Displays what language extensions are enabled. :run <name> <args> – Similar to :main. :unset – Undoes :set. Next you should become familiar with these commands for querying information about Haskell types and functions.

How to remove elements from a list in Haskell?

You have to split the list in two, remove the element from one list, and then join them back together, like this: (Related: tail xs removes the first element.) (Related: init xs removes the last element. Slow if the list is big.) Delete elements that meet some condition. Haskell has a function called filter which will do this for you.


Video Answer


2 Answers

How to sort list in ghci:

Prelude> :m + Data.List
Prelude Data.List> sort [1,4,2,0]
[0,1,2,4]

About your functions

let combineList xs ys = xs++ys

What is a point to create another alias for append function? But if you're really wants one - it could be defined like let combineList = (++).

let zs = combineList xs ys

It makes no sense because xs and ys are unknown outside of your combineList.

let sortList (z:zs) = if (head zs) < z then (zs:z) else (z:(sort zs))

This definition is not valid because it doesn't cover and empty list case and (zs:z) produces infinite type and sort is not defined yet. And you can get head of zs just by another pattern matching. And maybe you don't wanna to make another recursive call in the then part of if statement. And finally I should admit that this sorting algorithm doesn't work at all.

like image 172
ДМИТРИЙ МАЛИКОВ Avatar answered Oct 13 '22 16:10

ДМИТРИЙ МАЛИКОВ


It's a bit awkward to define a sorting function within the ghci. I thing the easiest way to do it would be to write the sorting function in a file, and then loading it into ghci. For instance, you could write this concise (though not in-place!) version of quicksort in a file called sort.hs (taken from the HaskellWiki):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (< p) xs
        greater = filter (>= p) xs

and load it into ghci:

> :l sort.hs 

If you really want to define the function in ghci, you can do something like this (from the Haskell user's guide):

> :{
> let { quicksort [] = []
>     ; quicksort (p:xs) = (quicksort (filter (< p) xs)) ++ [p] ++ (quicksort (filter (>= p) xs))
>     }
> :}

once this is defined, you can do

> let combineAndSort xs ys = quicksort (xs ++ ys)

As another answer already explained, it would of course be quicker to just import sort from Data.List, but it is definitely a good exercise to do it manually.

Your question suggests that you are a bit confused about the scope of variables in Haskell. In this line

> let combineList xs ys = xs++ys

you introduce the variables xs and ys. Mentioning them to the left of the equals sign just means that combineList takes two variables, and in the body of that function, you are going to refer to these variables as xs and ys. It doesn't introduce the names outside of the function, so the next line

> let zs = combineList xs ys

doesn't really make sense, because the names xs and ys are only valid within the scope of combineList. To make zs have a value, you need to give combineList some concrete arguments, eg.:

> let zs = combineList [2,4,6] [1,3,5]  --> [2,4,6,1,3,5]

But since the body of combineList is so simple, it would actually be easier to just do:

> let zs = [2,4,6] ++ [1,3,5] --> [2,4,6,1,3,5]

The last line is

> let sortList (z:zs) = if (head zs) < z then (zs:z) else (z:(sortList zs))

I think this line has confused you a lot, because there are quite a lot of different errors here. The answer by ДМИТРИЙ МАЛИКОВ mentions most of them, I would encourage you to try understand each of the errors he mentions.

like image 35
Boris Avatar answered Oct 13 '22 16:10

Boris